The Library
Better approximation guarantees for job-shop scheduling
Tools
Tools
Tools
Goldberg, Leslie Ann, Paterson, Michael S., Srinavasan, Aravind and Sweedyk, Elizabeth (1996) Better approximation guarantees for job-shop scheduling. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-312.pdf - Other - Requires a PDF viewer. Download (1442Kb) | Preview |
Abstract
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein and Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation guarantee. We improve the approximation guarantee of their work, and present further improvements for some important NP-hard special cases of this problem (e.g., in the preemptive case where machines can suspend work on operations and later resume). Some of these improvements represent the first constant-factor approximation algorithms. We also present NC algorithms with improved approximation guarantees for some NP-hard special cases.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Production scheduling -- Mathematical models | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | August 1996 | ||||
| Dates: |
|
||||
| Number: | Number 312 | ||||
| Number of Pages: | 14 | ||||
| DOI: | CS-RR-312 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | L.A. Goldberg, M.S. Paterson, A. Srinivasan and E. Sweedyk, “Better Approximation Guarantees for Job-shop Scheduling”, <i>Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, pp. 599-608 (1997) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
