Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time |
| |
Authors: | TCE Cheng CT Ng JJ Yuan |
| |
Institution: | 1. Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China;2. Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People’s Republic of China |
| |
Abstract: | 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. |
| |
Keywords: | Scheduling Single machine Multi-operation jobs Job-batch restriction SPT-agreeability |
本文献已被 ScienceDirect 等数据库收录! |
|