Single-machine total completion time scheduling with a time-dependent deterioration |
| |
| Authors: | Ji-Bo Wang Lin-Hui Sun Lin-Yan Sun |
| |
| Affiliation: | 1. School of Science, Shenyang Aerospace University, Shenyang 110136, China;2. School of Economics and Management, Xi’an University of Technology, Xi’an 710054, China;3. School of Management, Xi’an Jiaotong University, Xi’an 710049, China;4. The State Key Laboratory for Manufacturing Systems Engineering, Xi’an 710054,China;5. The Key Laboratory of the Ministry of Education for Process Control and Efficiency Engineering, Xi’an 710049, China;6. Knowledge Management and Innovation Research Centre of Xi’an Jiaotong University, Xi’an 710049, China |
| |
| Abstract: | In this paper, we consider the single-machine scheduling problems with a time-dependent deterioration. By the time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total completion time. We develop a mixed integer programming formulation for the problem. The complexity status of this problem remains open. Hence, we use the smallest normal processing time (SPT) first rule as a heuristic algorithm for the general cases and analyze its worst-case error bound. Two heuristic algorithms utilize the V-shaped property are also proposed to solve the problem. Computational results are presented to evaluate the performance of the proposed algorithms. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
