摘要
本文考虑将ｎ个互相独立的每道工序加工时长相等的工件放在两台机器上加工的自由作业排序问题。讨论了目标函数分别是带权完工时间和（Ｏ２／ＵＥＴ／Σｗｉｃｉ）及最大迟后（Ｏ２／ＵＥＴ／Ｌｍａｘ）两个问题，分别得到了计算时间限为Ｏ（ｎｌｏｇｎ）及Ｏ（ｎ２）的两个求解最优时间表的多项式算法。
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.
出处
《应用数学学报》
CSCD
北大核心
1995年第2期185-192,共8页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金
关键词
排序
自由作业
多项式算法
Scheduling
open shop
polynomial algorithm
