<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-312

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

L.A. Goldberg, M.S. Paterson, A. Srinivasan and E. Sweedyk, Better Approximation Guarantees for Job-shop Scheduling (August 1, 1996).

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.

<%@ include file="cited.html" %>

L.A. Goldberg, M.S. Paterson, A. Srinivasan and E. Sweedyk, "Better Approximation Guarantees for Job-shop Scheduling", Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 599-608 (1997)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>