文献类型：期刊文献

中文题名：两个可解的2×n自由作业排序问题

英文题名：TWO SOLVABLE TWO-MACHINE OPEN SHOP SCHEDULING PROBLEMS

作者：陈志龙[1];赵小平[1]

机构：[1]上海市城市综合交通规划研究所,华东化工学院应用数学研究所

年份：1995

卷号：18

期号：2

起止页码：185

中文期刊名：应用数学学报

外文期刊名：Acta Mathematicae Applicatae Sinica

收录：CSTPCD;;北大核心:【北大核心1992】；CSCD:【CSCD2011_2012】；

基金：国家自然科学基金

语种：中文

中文关键词：排序;自由作业;多项式算法

外文关键词：Scheduling; open shop; polynomial algorithm

摘要：本文考虑将ｎ个互相独立的每道工序加工时长相等的工件放在两台机器上加工的自由作业排序问题。讨论了目标函数分别是带权完工时间和（Ｏ２／ＵＥＴ／Σｗｉｃｉ）及最大迟后（Ｏ２／ＵＥＴ／Ｌｍａｘ）两个问题，分别得到了计算时间限为Ｏ（ｎｌｏｇｎ）及Ｏ（ｎ２）的两个求解最优时间表的多项式算法。
Considering the problems of scheduling n independent unit-execution-time jobs in a two-machine open shop, we discuss two problems, one is to minimize the total weighted completion times (O2/UET/Σwici) and the other is to minimize the maximum leteness (O2/UET/Lmax). A polynomial optimal solution algorithm is designed here for each of the problems respectively.