Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/1228
Title: | Scheduling with step-improving processing times | Authors: | Cheng, TCE He, Y Hoogeveen, H Ji, M Woeginger, GJ |
Issue Date: | Jan-2006 | Source: | Operations research letters, Jan. 2006, v. 34, no. 1, p. 37-40 | Abstract: | We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio. | Keywords: | Scheduling Knapsack problem Approximation scheme Competitive analysis |
Publisher: | Elsevier | Journal: | Operations research letters | ISSN: | 0167-6377 | EISSN: | 1872-7468 | DOI: | 10.1016/j.orl.2005.03.002 | Rights: | Operations Research Letters © 2005 Elsevier B.V. The journal web site is located at http://www.sciencedirect.com. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
step.pdf | Pre-published version | 96.62 kB | Adobe PDF | View/Open |
Page views
155
Last Week
1
1
Last month
Citations as of Mar 24, 2024
Downloads
203
Citations as of Mar 24, 2024
SCOPUSTM
Citations
5
Last Week
0
0
Last month
0
0
Citations as of Mar 28, 2024
WEB OF SCIENCETM
Citations
9
Last Week
0
0
Last month
0
0
Citations as of Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.