Minimizing makespan for mixed batch scheduling with identical machines and unequal ready times

Area of Science:

• Operations Research
• Industrial Engineering
• Computer Science

Background:

• Scheduling parallel batch machines involves complex processing times with setup, preheating, and heat preservation.
• Jobs exhibit variability in size, weight, and ready times, complicating optimization.
• Minimizing the makespan (total completion time) is a critical objective in such systems.

Purpose of the Study:

• To develop an efficient algorithm for minimizing makespan in parallel batch machine scheduling.
• To address the NP-hard nature of the problem with a novel heuristic approach.
• To validate the proposed model and algorithm against existing methods and optimal solutions.

Main Methods:

• Formulation of a mixed-integer linear programming (MILP) model for correctness verification.
• Development of a novel constructive heuristic algorithm employing a dynamic scheduling strategy.
• Analysis of algorithm time complexities and worst-case performance evaluation.
• Comparison of heuristic performance against MILP optimal solutions and lower bounds.

Main Results:

• The proposed constructive heuristic demonstrates superior scheduling performance compared to benchmark algorithms.
• The dynamic scheduling strategy effectively minimizes machine idle waiting time between batches.
• Experimental results validate the effectiveness of the new heuristic for both small and large-scale instances.

Conclusions:

• The novel constructive heuristic offers an effective solution for the NP-hard parallel batch scheduling problem.
• The dynamic scheduling approach significantly improves makespan minimization.
• This research provides a valuable contribution to optimizing batch processing systems.