A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine
type: Item
instance of: scholarly article
title: A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine
zbMATH Open document ID: 1198.90197
DOI: 10.1504/IJOR.2010.034069
author: G. Moslehi
author: Mehdi Mahnam
author: Majid Aminnayeri
author: Amir Azaron
published in: International Journal of Operational Research
publication date: 2010-11-12T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 5815545
zbMATH Keywords: single machine scheduling
zbMATH Keywords: earliness
zbMATH Keywords: tardiness
zbMATH Keywords: branch-and-bound
zbMATH Keywords: just-in-time
zbMATH Keywords: JIT production
MaRDI profile type: Publication
full work available at URL: ijor.2010.034069
OpenAlex ID: W2002220688
description: scientific article; zbMATH DE number 5815545