The Library

Better approximation guarantees for job-shop scheduling

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)

Preview

PDF (Department of Computer Science Research Report)
WRAP_cs-rr-312.pdf - Other - Requires a PDF viewer.
Download (1442Kb) | Preview

Request Changes to record.

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 > 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:

Date	Event
August 1996	Completion

Number:

Number 312

Number of Pages:

DOI:

CS-RR-312

Institution:

University of Warwick

Theses Department:

Department of Computer Science

Status:

Not Peer Reviewed

Publication Status:

Unpublished

Publisher Statement:

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: