An exact algorithm for single-machine scheduling without machine idle time |
| |
Authors: | Shunji Tanaka Shuji Fujikuma Mituhiko Araki |
| |
Affiliation: | (1) Institute of Computer Science, University of Wrocław, Joliot-Curie 15, 50-383 Wrocław, Poland |
| |
Abstract: | This study proposes an exact algorithm for the general single-machine scheduling problem without machine idle time to minimize
the total job completion cost. Our algorithm is based on the Successive Sublimation Dynamic Programming (SSDP) method. Its
major drawback is heavy memory usage to store dynamic programming states, although unnecessary states are eliminated in the
course of the algorithm. To reduce both memory usage and computational efforts, several improvements to the previous algorithm
based on the SSDP method are proposed. Numerical experiments show that our algorithm can optimally solve 300 jobs instances
of the total weighted tardiness problem and the total weighted earliness-tardiness problem, and that it outperforms the previous
algorithms specialized for these problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|