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: | Chu Chengbin, Kacem Imed, Souissi Ahmed |
Keywords: | programming: branch and bound, programming: integer, programming: dynamic |
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.