This paper considers the scheduling problem with rejection on m identical parallel machines to minimize the maximum flow time. The authors show that this problem is NP-hard even when there is a single machine and all ...This paper considers the scheduling problem with rejection on m identical parallel machines to minimize the maximum flow time. The authors show that this problem is NP-hard even when there is a single machine and all jobs have two distinct release dates. Furthermore, the authors present a dynamic programming algorithm and two approximation algorithms to solve them.展开更多
基金supported by the National Nature Science Foundation of China under Grant Nos.11426094,11271338 and U1504103
文摘This paper considers the scheduling problem with rejection on m identical parallel machines to minimize the maximum flow time. The authors show that this problem is NP-hard even when there is a single machine and all jobs have two distinct release dates. Furthermore, the authors present a dynamic programming algorithm and two approximation algorithms to solve them.
