Normal view MARC view

The Two-stage assembly scheduling problem: complexity and approximation

Author: Van Wassenhove, Luk N. ; Potts, Christopher N. ; Strusevitch, V.A ; Zwaneveld, C.M ; Sevast'janov, S. V.INSEAD Area: Technology and Operations Management Series: Working Paper ; 92/53/TM Publisher: Fontainebleau : INSEAD, 1992.Language: EnglishType of document: INSEAD Working Paper Online Access: Click here Abstract: This paper introduces a new two-stage assembly scheduling problem. There are m machines at the first stage each of which produces a component of a job. When all m components are avaible, a single assembly machine at the second stage completes the job. The objective is to schedule jobs on the machines so that the makespan is minimized. It is shown that the search for an optimal solution may be restricted to permutation schedules. The porblem is proved to be NP-hard in the strong sense even when m=2. A schedule associated with an arbitrary permutation of jobs is shown to provide a worst-case ratio bound of 2, and a heuristic with a worst-case ratio bound of 2-1/m is presented. The compact vector summation technique is applied for finding approximate solutions with worst-case absolute performance guarantees.
Tags: No tags from this library for this title. Add tag(s)
Log in to add tags.
Item type Current location Collection Call number Status Date due
INSEAD Working Paper Digital Library
PDF Available

This paper introduces a new two-stage assembly scheduling problem. There are m machines at the first stage each of which produces a component of a job. When all m components are avaible, a single assembly machine at the second stage completes the job. The objective is to schedule jobs on the machines so that the makespan is minimized. It is shown that the search for an optimal solution may be restricted to permutation schedules. The porblem is proved to be NP-hard in the strong sense even when m=2. A schedule associated with an arbitrary permutation of jobs is shown to provide a worst-case ratio bound of 2, and a heuristic with a worst-case ratio bound of 2-1/m is presented. The compact vector summation technique is applied for finding approximate solutions with worst-case absolute performance guarantees.

Digitized

There are no comments for this item.

Log in to your account to post a comment.
Koha 3.18 - INSEAD Library Catalogue
Library Home | Contact Us | What's Koha?