New Lower Bound Approach for Single-Machine Multicriteria Scheduling

摘要

The concept of maximum potential improvement has played an important role incomputing lower bounds for single machine scheduling problems with composite objective functions that are linear in the job completion times. A method for lower bound computation called objective splitting is introduced. The method is shown to dominate the maximum potential improvement method in terms of speed and quality.