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, 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.

• 저널Management Science · 26(3) · 274–281
• 토픽Advanced Optimization Algorithms Research · Numerical Analysis
• DOI10.1287/mnsc.26.3.274
• 저자Fred Shepardson, Roy E. Marsten