Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work |
| |
| Authors: | Yunqiang Yin Jianyou Xu T C E Cheng Chin‐Chia Wu Du‐Juan Wang |
| |
| Institution: | 1. Department of Mathematics, Kunming University of Science and Technology, Kunming, China;2. Department of Automation, College of Information Science and Engineering, Northeastern University, Shenyang, China;3. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;4. Department of Statistics, Feng Chia University, Taichung, Taiwan;5. Institute of Information and Decision Technology, School of Management Science and Engineering, Dalian University of Technology, Dalian, China |
| |
| Abstract: | We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016 |
| |
| Keywords: | scheduling late work fully polynomial‐time approximation scheme |
|
|
