کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477443 | 1446163 | 2008 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time](/preview/png/477443.png)
We consider the problem of scheduling multi-operation jobs on a singe machine to minimize the total completion time. Each job consists of several operations that belong to different families. In a schedule each family of job operations may be processed as batches with each batch incurring a set-up time. A job is completed when all of its operations have been processed. We first show that the problem is strongly NP-hard even when the set-up times are common and each operation is not missing. When the operations have identical processing times and either the maximum set-up time is sufficiently small or the minimum set-up time is sufficiently large, the problem can be solved in polynomial time. We then consider the problem under the job-batch restriction in which the operations of each batch is partitioned into operation batches according to a partition of the jobs. We show that this case of the problem can be solved in polynomial time under a certain condition.
Journal: European Journal of Operational Research - Volume 191, Issue 2, 1 December 2008, Pages 320–331