The two-stage assembly scheduling problem: Complexity and approximation

The two-stage assembly scheduling problem: Complexity and approximation

0.00 Avg rating0 Votes
Article ID: iaor19982230
Country: United States
Volume: 43
Issue: 2
Start Page Number: 346
End Page Number: 355
Publication Date: Mar 1995
Journal: Operations Research
Authors: , , , ,
Keywords: optimization
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 to 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.

Reviews

Required fields are marked *. Your email address will not be published.