文献类型：期刊文献

中文题名：安装、加工和拆卸时间分离的两台机器混合作业问题(英文)

英文题名：Two-Machine Mixed Shop Problem with Setup,Processing and Removal Time Separated

作者：刘朝晖[1];李毅[1]

机构：[1]华东理工大学数学系,上海200237

年份：2009

卷号：13

期号：4

起止页码：31

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

收录：CSTPCD;;CSCD:【CSCD2011_2012】；

基金：Supported by the National Natural Science Foundation of China under grant number 10771067

语种：中文

中文关键词：运筹学;排序;混合作业;算法

外文关键词：Operations research, scheduling, mixed shop, algorithm

摘要：混合作业是经典的自由作业和异序作业的一种综合,其中一些工件可以按任意的机器顺序进行处理,而另一些工件必须遵守预先指定的机器顺序.本文研究安装、加工和拆卸时间分离的两台机器混合作业排序问题,该问题已经被知道是强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.