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.