The Two-Stage Assembly Scheduling Problem: Complexity and Approximation

C. N. Potts, S. V. Sevast'janov, V. A. Strusevich, L. N. Van Wassenhove and C. M. Zwaneveld
Additional contact information
C. N. Potts: University of Southampton, Southampton, United Kingdom
S. V. Sevast'janov: Russian Academy of Sciences, Novosibirsk, Russian Federation
V. A. Strusevich: University of Greenwich, London, United Kingdom
L. N. Van Wassenhove: INSEAD, Fontainebleau, France
C. M. Zwaneveld: Erasmus University, Rotterdam, The Netherlands

Operations Research, 1995, vol. 43, issue 2, 346-355

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 available, 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. We show that the search for an optimal solution may be restricted to permutation schedules. The problem 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 two, and a heuristic with a worst-case ratio bound of 2 − 1/ m is presented. The compact vector summation technique is applied for finding approximation solutions with worst-case absolute performance guarantees.

Keywords: production/scheduling; assembly problem and complexity; production/scheduling; approximations/heuristic; worst-case analysis (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (33)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.2.346 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:43:y:1995:i:2:p:346-355

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().