Abstract:

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.  

Key words: parallel machine scheduling, eligibility restriction, makespan, unit-length