摘要
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．
出处
《运筹学学报》
CSCD
1998年第1期71-78,共8页
Operations Research Transactions
基金
国家自然科学基金
安徽省教委科研基金
关键词
自由作业
排序
指派问题
加工时间
簅pen－shop； scheduling， assignment problem， optimal algorithm
