机器和工人都有加工资质约束的平行机排序问题研究

研究一类新型的平行机排序问题, 即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下, 如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_max. 将研究工件加工时间均为单位时间的情况, 通过建立网络流模型以及采用二分搜索技术, 可以在多项式时间内精确地求解上述问题, 算法复杂度为O(n^{3}logn). 同时提供了一种基于双重动态柔性选择,(DDFS),策略的启发式算法,可以获得较好的排序效果, 算法复杂度为O(n^{2}).

Parallel machine scheduling with machine and human eligibility restrictions

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.