Citation
An exact algorithm for single-machine scheduling without machine idle time. Journal of Scheduling, 12 (6): 575-593, 2009.
Selected
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.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/s10951-008-0093-5 You can link directly to the original paper, via the doi, from here
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@ARTICLE{2009-575-593-SI, author = {S. Tanaka and S. Fujikuma and M. Araki},
title = {An exact algorithm for single-machine scheduling without machine idle time},
journal = {Journal of Scheduling},
year = {2009},
volume = {12},
pages = {575--593},
number = {6},
note = {Selected},
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.},
doi = {10.1007/s10951-008-0093-5},
owner = {user},
timestamp = {2012.05.25} }