Lot-sizing scheduling with batch setup times
Chen, Bo, Dr., Ye, Yinyu and Zhang, Jiawei. (2006) Lot-sizing scheduling with batch setup times. Journal of Scheduling, Vol.9 (No.3). pp. 299-310. ISSN 1094-6136Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s10951-006-8265-7
This paper is concerned with scheduling independent jobs on m parallel machines in such a way that the makespan is minimized. Each job j is allowed to split arbitrarily into several parts, which can be individually processed on any machine at any time. However, a setup for uninterrupted s(j) time units is required before any split part of job j can be processed on any machine. The problem is strongly NP-hard if the number m of machines is variable and weakly NP-hard otherwise. We give a polynomial-time 5/3-approximation algorithm for the former case and a fully polynomial-time approximation scheme for the latter.
|Item Type:||Journal Article|
|Subjects:||T Technology > TS Manufactures
H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management
|Divisions:||Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences
Faculty of Social Sciences > Warwick Business School
|Journal or Publication Title:||Journal of Scheduling|
|Publisher:||Springer New York LLC|
|Official Date:||June 2006|
|Number of Pages:||12|
|Page Range:||pp. 299-310|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)