Makespan minimization for two parallel machines scheduling with a periodic availability constraint |
| |
| Authors: | Dehua Xu Zhenmin Cheng Yunqiang Yin Hongxing Li |
| |
| Affiliation: | 1. School of Mathematical Sciences, Beijing Normal University, Beijing 100875, China;2. School of Electronic and Information Engineering, Dalian University of Technology, Dalian 116024, China |
| |
| Abstract: | A two parallel machines scheduling problem where one machine is periodically unavailable with the objective of minimizing makespan is considered. It is showed that the worst-case ratio of the classical LPT algorithm and the competitive ratio of the LS algorithm are 3/2 and 2, respectively, for the offline version and the online version of the problem. |
| |
| Keywords: | Scheduling Parallel machine Availability Heuristic algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
