Minimizing the weighted sum of squared tardiness on a single machine

Minimizing the weighted sum of squared tardiness on a single machine

0.00 Avg rating0 Votes
Article ID: iaor20118777
Volume: 39
Issue: 5
Start Page Number: 919
End Page Number: 928
Publication Date: May 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: manufacturing industries, combinatorial optimization, programming: branch and bound
Abstract:

This paper considers a problem in which there is a set of jobs to be sequenced on a single machine. Each job has a weight and the objective is to sequence the jobs to minimize total weighted squared tardiness. A branch‐and‐bound algorithm is developed for optimally solving the problem. Several dominance conditions are presented for possible inclusion in the branch‐and‐bound algorithm. The dominance conditions are included in the branch‐and‐bound algorithm, which is tested on randomly generated problems of various numbers of jobs, due date tightness and due date ranges. The results show that the dominance conditions dramatically improve the efficiency of the branch‐and‐bound algorithm.

Reviews

Required fields are marked *. Your email address will not be published.