Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times

Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times

0.00 Avg rating0 Votes
Article ID: iaor2009970
Country: United Kingdom
Volume: 35
Issue: 3
Start Page Number: 827
End Page Number: 844
Publication Date: Mar 2008
Journal: Computers and Operations Research
Authors: , ,
Keywords: programming: branch and bound, programming: integer, programming: dynamic
Abstract:

In this article, we consider a single-machine scheduling problem with one unavailability period, with the aim of minimizing the weighted sum of the completion times. We propose three exact methods for solving such a problem: a branch-and-bound method based on new properties and lower bounds, a mixed integer programming model, and a dynamic programming method. These methods were coded and tested on randomly generated instances, and their performances were analyzed. Our numerical experiments show that the branch-and-bound method and the dynamic programming method are complementary. Using these approaches, we are able to solve problems with up to 3000 jobs within a reasonable computation time.

Reviews

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