|
|||||
|
|
Lot-sizing scheduling with batch setup times |
|
| Authors: | Bo Chen Yinyu Ye Jiawei Zhang |
| Affiliation: | (1) Warwick Business School, University of Warwick, Coventry, CV4 7AL, UK;(2) Department of Management Science and Engineering, School of Engineering, Stanford University, Stanford, CA 94305, USA;(3) Department of Information, Operations, and Management Sciences, Stern School of Business, New York University, NY, 10012-1126, USA |
| Abstract: | 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 sj 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  -approximation algorithm for the former case and a fully polynomial-time approximation scheme for the latter. AMS Subject Classifications: 68M20 · 90B35 · 90C59 |
| Keywords: | Scheduling Lot-sizing Batch setup time Approximation algorithm Approximation scheme |
| 本文献已被 SpringerLink 等数据库收录！ | |