Scheduling deteriorating jobs on a single machine with release times |
| |
| Authors: | Wen-Chiung Lee Chin-Chia Wu Yu-Hsiang Chung |
| |
| Affiliation: | 1. Department of Computer Engineering, Wroc?aw University of Technology, Janiszewskiego 11-17, 50-372 Wroc?aw, Poland;2. Department of Control Systems and Mechatronics, Wroc?aw University of Technology, Janiszewskiego 11-17, 50-372 Wroc?aw, Poland;1. Department of Economics and Business Administration, Ariel University, Israel;2. School of Business Administration, The Hebrew University, Jerusalem 91905, Israel;3. Department of Industrial Engineering and Management, Ben-Gurion University, Beer Sheva, Israel;1. Department of Automatics, Mechatronics and Control Systems, Faculty of Electronics, Wroc?aw University of Technology, Janiszewskiego 11-17, 50-372 Wroc?aw, Poland;2. Wroc?aw Centre of Networking and Supercomputing, Wyb. Wyspiańskiego 27, 50-370 Wroc?aw, Poland;3. Institute of Computer Science, University of Wroc?aw, Joliot-Curie 15, 50-383 Wroc?aw, Poland;1. Department of Healthcare Management, Yuanpei University, Hsinchu, Taiwan;2. College of Information Science and Engineering, Northeastern University, Shenyang 110819, China;3. Department of Business Administration, Kang-Ning Junior College, Taipei, Taiwan;4. State Key Laboratory Breeding Base of Nuclear Resources and Environment, East China Institute of Technology, Nanchang 330013, China;5. Department of Statistics, Feng Chia University, Taichung, Taiwan |
| |
| Abstract: | This paper investigates a single-machine deteriorating job scheduling problem with job release times where its objective is to minimize the makespan. The problem is known to be NP-hard. Therefore, a branch-and-bound algorithm incorporating with several dominance properties and lower bounds is proposed to derive the optimal solution for the problem. In addition, easy-implemented heuristic algorithms are also provided to obtain the near-optimal solution. The computational experiments indicate that the branch-and-bound algorithm can solve most of the medium-job-sized problems within a reasonable time, and the heuristic is quite accurate with an average error percentage of less than 0.3%. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
