Earliness and tardiness scheduling problems on a batch processor

Earliness and tardiness scheduling problems on a batch processor

0.00 Avg rating0 Votes
Article ID: iaor20003428
Country: Netherlands
Volume: 98
Issue: 1/2
Start Page Number: 131
End Page Number: 145
Publication Date: Nov 1999
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: programming: dynamic
Abstract:

In this paper, we discuss the problem of scheduling n jobs on a batch processor to minimize total earliness and tardiness. We propose a dynamic programming algorithm in polynomial time to show the problem is polynomially solvable. However, the algorithm is not efficient in practice because of the high exponent and large memory requirement. We then propose a dynamic programming algorithm to solve the problem in pseudopolynomial time. We also extend our analysis to the cases of weighted earliness and tardiness problems, jobs with agreeable release times, and jobs with due windows. Finally, we report and discuss computational results.

Reviews

Required fields are marked *. Your email address will not be published.