Asymptotic analysis of SPTA-based algorithms for no-wait flow shop scheduling problem with release dates

Area of Science:

• Operations Research
• Industrial Engineering
• Manufacturing Systems

Background:

• The no-wait flow shop scheduling problem is critical for manufacturing efficiency.
• Optimizing total completion time with release dates presents significant computational challenges.
• Existing algorithms may lack performance guarantees for varying problem scales.

Purpose of the Study:

• To develop and analyze algorithms for the no-wait flow shop scheduling problem.
• To optimize the total completion time objective considering job release dates.
• To provide methods effective for both large and moderate-sized problem instances.

Main Methods:

• Asymptotic analysis to establish convergence properties of algorithms.
• Shortest Processing Time Among Available (SPTA)-based algorithms.
• Local search-based improvement scheme for enhanced performance.
• Development of a new lower bound for assessing asymptotic optimality.

Main Results:

• Two SPTA-based algorithms demonstrate convergence to optimal total completion time for large-scale problems.
• The local search scheme effectively enhances algorithm performance for moderate-sized instances.
• The new lower bound aids in evaluating the asymptotic optimality of scheduling algorithms.

Conclusions:

• The proposed SPTA-based algorithms offer effective solutions for the no-wait flow shop scheduling problem.
• The combination of asymptotic analysis and local search provides a robust approach across different problem scales.
• The study contributes improved methods for optimizing manufacturing scheduling with release dates.