Scheduling tool changes and special jobs on a single machine to minimize makespan |
| |
Authors: | Dehua Xu Min Liu Yunqiang Yin Jinghua Hao |
| |
Affiliation: | 1. State Key Laboratory Breeding Base of Nuclear Resources and Environment, East China Institute of Technology, Nanchang, Jiangxi 330013, PR China;2. School of Science, East China Institute of Technology, Fuzhou, Jiangxi 344000, PR China;3. Department of Automation, Tsinghua University, Beijing 100084, PR China |
| |
Abstract: | This paper considers a variation of the classical single machine scheduling problem with tool changes. In the variation, two sets of jobs, namely special jobs and normal jobs, are considered. By special jobs, we mean that each special job must be processed within the first prefixed time units of a tool life. To solve the scheduling problem with small size and moderate size, we propose two mathematical programming models. To solve the scheduling problem with large size, we propose three sets of algorithms and focus on the performance of six algorithms based on the studies of a new bin packing problem. Worst-case analysis is conducted. Numerical experiment shows that each of the six algorithms can solve instances with up to 5000 jobs in about 0.5 s with an average relative error less than 4%. |
| |
Keywords: | Scheduling Mathematical programming model Bin packing Approximation algorithm Tool change |
本文献已被 ScienceDirect 等数据库收录! |
|