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

Authors: Ghasem Moslehi, Mehdi Mahnam, Majid Amin-Nayeri, Amir Azaron

Addresses: Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156 83111, Iran. ' Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156 83111, Iran. ' Department of Industrial Engineering, Amirkabir University of Technology, 424 Hafez Avenue, Tehran, Iran. ' Michael Smurfit Graduate School of Business, University College Dublin, Carysfort Avenue, Blackrock, Dublin, Ireland

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.

DOI: 10.1504/IJOR.2010.034069

International Journal of Operational Research, 2010 Vol.8 No.4, pp.458 - 482

Published online: 07 Jul 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article