A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine

Ghasem Moslehi, Mehdi Mahnam, Majid Amin-Nayeri and Amir Azaron

International Journal of Operational Research, 2010, vol. 8, issue 4, 458-482

Abstract: In this paper, we consider the problem of scheduling n jobs on a single machine to minimise the sum of maximum earliness and tardiness. Since this problem is trying to minimise the earliness and tardiness values, the model is consistent with the just-in-time production system. Most of publications on this subject have studied 'min-sum' objective functions, but in many settings balancing the costs of the jobs by minimising the cost of the worst scheduled job as 'min-max' criteria is more important. Using efficient lower and upper bounds and new dominance rules, a branch-and-bound scheme is proposed. The proposed algorithm is then tested on a set of randomly generated problems of different sizes, varying from 5 to 1,000 jobs. Using these approaches, we are able to solve all problems in a reasonable time. Computational results demonstrate the efficiency of our branch-and-bound algorithm over the existing methods reported in the literature.

Keywords: single machine scheduling; earliness; tardiness; branch-and-bound; just-in-time; JIT production. (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=34069 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:8:y:2010:i:4:p:458-482

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().