A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time |
| |
Authors: | Email author" target="_blank">Shunji?TanakaEmail author Shuji?Fujikuma |
| |
Affiliation: | 1.Department of Electrical Engineering,Kyoto University,Kyoto,Japan |
| |
Abstract: | This paper proposes an efficient exact algorithm for the general single-machine scheduling problem where machine idle time
is permitted. The algorithm is an extension of the authors’ previous algorithm for the problem without machine idle time,
which is based on the SSDP (Successive Sublimation Dynamic Programming) method. We first extend our previous algorithm to
the problem with machine idle time and next propose several improvements. Then, the proposed algorithm is applied to four
types of single-machine scheduling problems: the total weighted earliness-tardiness problem with equal (zero) release dates,
that with distinct release dates, the total weighted completion time problem with distinct release dates, and the total weighted
tardiness problem with distinct release dates. Computational experiments demonstrate that our algorithm outperforms existing
exact algorithms and can solve instances of the first three problems with up to 200 jobs and those of the last problem with
up to 80 jobs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|