A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling Problem

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 56 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.