A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling Problem

The two duty period scheduling problem is an integer programming problem with 0-1 constraint coefficients. It is recognized that the problem can be reformulated as a one duty period problem with side constraints. Since the one duty period problem can be solved as a minimal cost network flow problem,...

Full description

Saved in:
Bibliographic Details
Published in:Management science 1980-03, Vol.26 (3), p.274-281
Main Authors: Shepardson, Fred, Marsten, Roy E
Format: Article
Language:English
Subjects:
Algorithms
City buses
Educational administration
Fortran
Incumbents
Integer programming
Integers
Linear programming
Management science
Mathematics
Minimization of cost
Optimization
production
Production scheduling
production/scheduling: personnel
programming: integer algorithms
Scheduling
scheduling: personnel
Sleep deprivation
Truck drivers
Variables
Workforce planning
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The two duty period scheduling problem is an integer programming problem with 0-1 constraint coefficients. It is recognized that the problem can be reformulated as a one duty period problem with side constraints. Since the one duty period problem can be solved as a minimal cost network flow problem, we dualize with respect to the side constraints, forming a Lagrangean relaxation which is easily solved. Subgradient optimization is used to maximize the Lagrangean. Computational results are reported for several large problems.
ISSN:0025-1909
1526-5501
DOI:10.1287/mnsc.26.3.274