Operations Research Transactions >
2018 , Vol. 22 >Issue 3: 99 - 108
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2018.03.010
Parallel machine scheduling with machine and human eligibility restrictions
Received date: 2017-11-17
Online published: 2018-09-15
This paper considers the problem of parallel machine scheduling where both machine and human are essential resources with eligibility restrictions, the objective is to minimize the makespan. We focus on the case of unit-length jobs. Based on max-flow model and binary search algorithm, the problem can be solved in polynomial time with the bound of O(n^{3}logn). We further present an O(n^{2}) effective heuristic based on dual danymic flexibility selection(DDFS) strategy, which can achieve close or exact solution to optimality.
ZHAO Xiaocheng, LI Dagang . Parallel machine scheduling with machine and human eligibility restrictions[J]. Operations Research Transactions, 2018 , 22(3) : 99 -108 . DOI: 10.15960/j.cnki.issn.1007-6093.2018.03.010
/
| 〈 |
|
〉 |