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