The concept of maximum potential improvement has played an important role in computing lower bounds for single-machine scheduling problems with composite objective functions that are linear in the job completion times. We introduce a new method for lower bound computation; objective splitting. We show that it dominates the maximum potential improvement method in terms of speed and quality.
- Single-machine scheduling
- Multicriteria scheduling
- Maximum potential improvement
- Objective splitting
Hoogeveen, J. A., & van de Velde, S. L. (1992). A new lower bound approach for single-machine multicriteria scheduling. Operations research letters, 0(11), 39-44. https://doi.org/10.1016/0167-6377(92)90060-G