摘要
混合作业是经典的自由作业和异序作业的一种综合,其中一些工件可以按任意的机器顺序进行处理,而另一些工件必须遵守预先指定的机器顺序.本文研究安装、加工和拆卸时间分离的两台机器混合作业排序问题,该问题已经被知道是强NP困难的,本文把流水作业中的同顺序作业概念推广到混合作业,并得到这个混合作业问题在同顺序意义下的最优解,这个解对于一般情形是3/2近似解,但对于一些有意义的特殊情形是整体最优的.
A mixed shop is the combination of an open shop and a job shop, where some jobs can be processed in arbitrary machine orders, while the other jobs must follow fixed machine orders. In this paper, we consider the two-machine mixed shop scheduling problem with setup, processing and removal times separated. The problem has been known strongly NP-hard. We generalize the permutation schedule concept of the flow shop, and present a simple algorithm to find a best permutation schedule that is a 3/2- approximation and is globally optimal for some interesting special cases.
出处
《运筹学学报》
CSCD
2009年第4期31-38,共8页
Operations Research Transactions
基金
Supported by the National Natural Science Foundation of China under grant number 10771067
关键词
运筹学
排序
混合作业
算法
Operations research, scheduling, mixed shop, algorithm
