Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times |
| |
Authors: | Imed Kacem Chengbin Chu Ahmed Souissi |
| |
Affiliation: | Université de Technologie de Troyes, ICD, LOSI FRE CNRS 2848, 12 rue Marie Curie, BP 2060, Troyes, France |
| |
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. |
| |
Keywords: | Scheduling Availability constraint Branch and bound Integer programming Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |
|