A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine. (8th July 2010)

• Record Type: Journal Article
• Authors: Moslehi, Ghasem; Mahnam, Mehdi; Amin-Nayeri, Majid; Azaron, Amir
• Is Part Of: International journal of operational research. Volume 8:Number 4(2010)
• Page Start: 458
• Page End: 482
• Publication Date: 2010-07-08
• Subjects: single machine scheduling -- earliness -- tardiness -- branch-and-bound -- just-in-time -- JIT production; Operations research -- Periodicals; 003.05
• Languages: English
• ISSNs: 1745-7645

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.