|
|||||
|
|
Parallel-machine scheduling with an availability constraint |
|
| Authors: | Chuanli Zhao Min Ji Hengyong Tang |
| Affiliation: | aSchool of Mathematics and Systems Science, Shenyang Normal University, Shenyang, Liaoning 110034, PR China;bSchool of Computer Science and Information Engineering, Contemporary Business and Trade Research Center, Zhejiang Gongshang University, Hangzhou, Zhejiang 310018, PR China |
| Abstract: | e consider two parallel machines scheduling problem where one machine is not available in a specified time period. The unavailable time period is fixed and known in advance. The objective is to minimize the total weighted completion time. The problem is known to be NP-hard. We give a fully polynomial-time approximation scheme (FPTAS) for the problem. We then generalize the results to the case with m parallel machines. |
| Keywords: | Scheduling Machine availability constraint Parallel machine FPTAS |
| 本文献已被 ScienceDirect 等数据库收录！ | |