A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling Problem
Fred Shepardson, Roy E. Marsten
Management Science · 1980 · Volume 26 · Issue 3
Abstract
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.
Keywords
production/scheduling: personnel, programming: integer algorithms
Enable JavaScript for citation tools and additional paper interactions.