Single machine scheduling problems with sequence-dependent setup times and precedence delays

Area of Science:

• Operations Research
• Industrial Engineering
• Manufacturing Systems

Background:

• Sequence-dependent setup times and precedence delays are common challenges in production environments.
• These factors complicate scheduling and impact overall efficiency.
• Optimizing schedules is crucial for minimizing production lead times.

Purpose of the Study:

• To address the single machine scheduling problem with setup times and precedence delays.
• To develop a novel mixed-integer linear programming model and an efficient algorithm.
• To minimize the makespan in an amplifier assembly company context.

Main Methods:

• Development of a novel mixed-integer linear programming model.
• Introduction of a lean iterated greedy (LIG) algorithm.
• Utilizing a lean construction mechanism to discard infeasible solutions and accelerate convergence.

Main Results:

• The LIG algorithm demonstrates superior performance compared to state-of-the-art methods.
• Significant improvements in both solution quality and computational efficiency were observed.
• The algorithm effectively handles delayed precedence constraints.

Conclusions:

• The proposed LIG algorithm offers a simple, effective, and efficient solution for complex scheduling problems.
• This research provides a valuable tool for industrial applications in manufacturing.
• The study establishes a new benchmark for future research in scheduling optimization.