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

作者：赵晓成^*; 李大刚

来源：运筹学学报, 2018, 22(03): 99-108.

DOI：10.15960/j.cnki.issn.1007-6093.2018.03.010

• 平行机排序
• 加工资质约束
• 时间表长
• 单位时间

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

• 单位
  北京大学深圳研究生院