Scheduling linear deteriorating jobs to minimize the number of tardy jobs
AbstractIn this paper a problem of scheduling a single machine under linear deterioration which aims at minimizing the number of tardy jobs is considered. According to our assumption, processing time of each job is dependent on its starting time based on a linear function where all the jobs have the same deterioration rate. It is proved that the problem is NP-hard; hence a branch and bound procedure and a heuristic algorithm with O(n 2 ) is proposed where the heuristic one is utilized for obtaining the upper bound of the B&B procedure. Computational results for 1,800 sample problems demonstrate that the B&B method can solve problems with 28 jobs quickly and in some other groups larger problems are also solved. Generally, B&B method can optimally solve 85% of the samples which shows high performance of the proposed method. Also it is shown that the average value of the ratio of optimal solution to the heuristic algorithm result with the objective ∑(1 − Ui) is at most 1.11 which is more efficient in comparison to other proposed algorithms in related studies in the literature. Copyright Springer Science+Business Media, LLC. 2012
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Springer in its journal Journal of Global Optimization.
Volume (Year): 54 (2012)
Issue (Month): 2 (October)
Contact details of provider:
Web page: http://www.springer.com/business/operations+research/journal/10898
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- M'Hallah, Rym & Bulfin, R. L., 2003. "Minimizing the weighted number of tardy jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 145(1), pages 45-56, February.
- Chen, Wen-Jinn, 2009. "Minimizing number of tardy jobs on a single machine subject to periodic maintenance," Omega, Elsevier, vol. 37(3), pages 591-599, June.
- M'Hallah, Rym & Bulfin, R.L., 2007. "Minimizing the weighted number of tardy jobs on a single machine with release dates," European Journal of Operational Research, Elsevier, vol. 176(2), pages 727-744, January.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Guenther Eichhorn) or (Christopher F Baum).
If references are entirely missing, you can add them using this form.