有模具约束的平行机台最小拖期和调度问题  

Minimize total tardiness of the parallel machine with modulo constrain

作　　者：王成尧[1] 高麟[1] 汪定伟[1] 殷秩松[2] 王书宁[2] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110006 [2]清华大学自动化系,北京100084

出　　处：《系统工程学报》1999年第4期345-350,共6页Journal of Systems Engineering

基　　金：国家自然科学基金;灿坤电器实业股份有限公司资助

摘　　要：针对某电器企业的一个瓶颈工序来制定调度方案，该问题归纳为平行机台具有模具约束，目标为最小拖期和的调度问题．本文提出了如下的启发式算法：根据模具情况运用成组技术对工作成组并生成运行表：按运行表顺序对各个运行中的工作进行指派机台，设置禁忌模具集合，避免对运行的短视性；根据工作的交货期和加工时间选择适当的机台进行加工；在各个机台运用ＮＢＲ（ＮｅｔＢｅｎｅｆｉｔｏｆＲｅｌｏｃａｔｉｏｎ）算法调节顺序以减少拖期和．该算法在厂家的实际测试中，通过三个不同的实例与手工排程进行了比较，各项指标均有明显优势．This paper develops a scheduling method for a bottleneck course of an electrical enterprise, it is a problem that minimizes the total tardiness of jobs processing in parallel machine with modulo constrains. A heuristic algorithm is developed. Firstly, we employ group technology by grouping jobs under modulo constrains to produce run list. Secondly, when assign each job of the run to the machine, under a taboo list of modulo that is set to avoid myopic modulo,we assign each job by its due date and processing times. Finally, after all jobs were assigned, we employ NBR (net benefit of relocation)algorithm to adjust the sequence of jobs on each machine for minimizing total tardiness. Compared with scheduling by manual, the heuristic algorithm has high speed and excellent efficiency.

关 键 词：成组技术 调度问题 启发式算法 平行机台 

分 类 号：O224[理学—运筹学与控制论]