二台机器自由作业总流程的一种改进方法  

The Improvement of the Total Flow-time of Two Machine Open-shop

作　　者：刘林[1] LIU Lin(School of Mathematics,Zhengzhou University of Aeronautics,Zhengzhou 450046,China)

机构地区：[1]郑州航空工业管理学院数学学院,河南郑州450046

出　　处：《郑州航空工业管理学院学报》2023年第1期97-100,108,共5页Journal of Zhengzhou University of Aeronautics

摘　　要：基于1992年M.Dror提出的工件加工时间依赖机器的排序问题,研究以最大完工时间和以总完工时间为优化目标的两类排序问题。二台机器自由作业总流程问题为NP-困难问题,加工时间仅依赖于机器的两台机器自由作业排序问题可转化成指派问题,并且可以构造出这一问题的显式解。文章利用不允许机器空闲的条件下该问题的最优解,给出允许机器空闲而使完工时间总和减少的一种方法,说明在一定条件下不允许机器空闲的显式解一定不是允许机器空闲的显式解。Based on the scheduling problem of machine-dependent workpiece pracesing time proposed by M.Dror in 1992,this paper studied two kinds of scheduling problems with maximum completion time and total completion time as optimization objectives.The total flow problem of two machine open-shop is NP-hard.The scheduling problem of two machine open-shop whose processing time depends only on the machine can be transformed into an assignment problem and its explicit solution can be constructed.In this paper,a method of reducing the total completion time by allowing the machine to be idle is given by using the optimal solution of the problem under the condition that the machine is not idle.It is proved that an explicit solution that does not allow the machine to be idle under certain conditions must not be an explicit solution that allows the machine to be idle.

关 键 词：自由作业 总流程 显式解 时间表 

分 类 号：O157[理学—数学]