English

运筹学学报

• 运筹学 • 上一篇    下一篇

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

赵晓成1,* 李大刚1   

  1. 1. 北京大学深圳研究生院信息工程学院, 广东深圳 518055
  • 收稿日期:2017-11-17 出版日期:2018-09-15 发布日期:2018-09-15
  • 通讯作者: 赵晓成 E-mail: 598029804@qq.com

Parallel machine scheduling with machine and human eligibility restrictions

ZHAO Xiaocheng1,*  LI Dagang1   

  1. 1. School of Electronic and Computer Engineering, Peking University Shenzhen Graduate School, Shenzhen 518055, Guangdong, China
  • Received:2017-11-17 Online:2018-09-15 Published:2018-09-15

PDF

105

摘要：

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

关键词: 平行机排序, 加工资质约束, 时间表长, 单位时间

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