加工时间依赖于机器的自由作业排序问题  

Open-Shop Scheduling Problem with Machine Dependent Pr0cessing Times

作　　者：项思明[1] 唐国春[2] 

机构地区：[1]安徽建筑工业学院,安徽230022 [2]上海第二工业大学,上海200041

出　　处：《运筹学学报》1998年第1期71-78,共8页Operations Research Transactions

基　　金：国家自然科学基金;安徽省教委科研基金

摘　　要：1992年M．Dror提出工件的加工时间依赖于机器的排序问题（schedulingwithmachinedependentprocessingtimes），并研究以最大完工时间（makespan）和以总的完工时间为优化目标的两种这类排序问题．然而，M．Dror对以总的完工时间为优化目标提出的“最优算法”是错误的．本文用算例表明他提出的算法不是最优的，并在机器连续加工的条件下，把这个排序问题转化成指派问题（assignmentproblem），从而可以用匈牙利算法得到最优解．最后，我们提出几个尚未解决的问题，以期引起国内外同行进一步研究．M.Dror examined the open-shop scheduling problem with machine dependent processing times in 1992. Two criteria were considered: minimizing the maximum completion time (makespan), and minimizing the total completion time. In this paper we show that the 'algorithm' for the second criterion proposed by him is wrong. Then, we formulate the problem to minimize the total completion time as an asslgnoment model when machines are continuously available and are never kept idle while work is walting， and apply the Hungarian method to solve it． Several questions are still unanswered．We describe tree open problems for further research at last．

关 键 词：自由作业 排序 指派问题 加工时间 

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