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 |
Access
View full-text via PolyU eLinks 
Page views
225
Last Week
1
1
Last month
Citations as of Aug 13, 2025
Downloads
251
Citations as of Aug 13, 2025
SCOPUSTM
Citations
7
Last Week
0
0
Last month
0
0
Citations as of Dec 19, 2025
WEB OF SCIENCETM
Citations
11
Last Week
0
0
Last month
0
0
Citations as of Dec 18, 2025
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.