EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2195. Flow shops with reentry: Total completion time optimal schedules
Invited abstract in session WD-60: Flow shop and single machine scheduling , stream Project Management and Scheduling.
Wednesday, 14:30-16:00Room: S09 (building: 101)
Authors (first author is the speaker)
| 1. | Nicklas Klein
|
| Department of Business Administration, University of Bern | |
| 2. | Michael Pinedo
|
| Leonard N. Stern School of Business, New York University |
Abstract
Flow shops are widely studied machine environments in which all jobs must visit all machines in the same order. While conventional flow shops assume that each job traverses the shop only once, many industrial environments require jobs to pass through the shop multiple times before completion, i.e., after traversing the shop and completing its processing on the last machine, a job must return to the first machine and traverse the shop again until it has completed all its required loops. There are numerous applications, e.g., in semiconductor manufacturing, of such a setting, which is called a flow shop with reentry. The planning problem is to schedule all loops of all jobs while minimizing the total (weighted) completion time. We consider a reentrant flow shop with unit processing times and show that the Least Remaining Loops First (LRL) priority rule minimizes the total completion time. Furthermore, we show that the problem of minimizing the total weighted completion time is NP-hard. For this objective, we show that the Weighted Least Remaining Loops First (WLRL) priority rule has a worst-case performance ratio of about 1.2.
Keywords
- Scheduling
- Complexity and Approximation
- Manufacturing
Status: accepted
Back to the list of papers