Parallel batch scheduling of deteriorating jobs with release dates and rejection

Area of Science:

• Operations Research
• Computer Science
• Discrete Mathematics

Background:

• Batch scheduling problems are crucial in manufacturing and computing.
• Job deterioration and rejection introduce complexities in scheduling.
• Minimizing makespan and penalties is a common optimization objective.

Purpose of the Study:

• To investigate the unbounded parallel batch scheduling problem with deterioration, release dates, and rejection.
• To develop efficient algorithms for minimizing the sum of makespan and rejection penalties.
• To analyze the computational complexity and provide optimal solutions for specific cases.

Main Methods:

• Problem formulation as a minimization problem involving makespan and penalties.
• Proof of NP-hardness for the general problem.
• Development of pseudopolynomial time algorithms and a fully polynomial-time approximation scheme (FPTAS).
• Design of an optimal O(n log n) algorithm for identical release dates.

Main Results:

• The general parallel batch scheduling problem with deterioration, release dates, and rejection is NP-hard.
• Efficient algorithms, including an FPTAS, are proposed for practical solutions.
• An optimal and efficient O(n log n) algorithm is derived for the specific case of identical release dates.

Conclusions:

• The study provides a comprehensive analysis of a complex scheduling problem.
• The developed algorithms offer effective solutions for minimizing makespan and penalties.
• The findings contribute to the theoretical understanding and practical application of scheduling optimization.