Two-machine shop scheduling with zero and unit processing times

被引：3
作者：
Lushchakova, IN
Kravchenko, SA
机构：
[1] Belarusian State Univ Informat & Radioelect, Minsk 220027, BELARUS
[2] Inst Engn Cybernet, Minsk 220012, BELARUS
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1998年 / 107卷 / 02期
关键词：
flow shop; open shop; optimal schedule; polynomial algorithm;
D O I：
10.1016/S0377-2217(97)00337-8
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider the two machine flow shop and open shop problems to minimize the weighted mean flow-time, processing times being equal to 0 or 1. The solution to the open shop problem is based on algorithms for the flow shop problem and the corresponding two parallel identical machine problem. For all problems O(n log n) algorithms are proposed. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：378 / 388
页数：11
相关论文
共 15 条
  • [1] SCHEDULING THE OPEN SHOP TO MINIMIZE MEAN FLOW TIME
    ACHUGBUE, JO
    CHIN, FY
    [J]. SIAM JOURNAL ON COMPUTING, 1982, 11 (04) : 709 - 720
  • [2] Brucker P., 1993, ZOR, Methods and Models of Operations Research, V37, P59, DOI 10.1007/BF01415528
  • [3] SCHEDULING INDEPENDENT TASKS TO REDUCE MEAN FINISHING TIME
    BRUNO, J
    COFFMAN, EG
    SETHI, R
    [J]. COMMUNICATIONS OF THE ACM, 1974, 17 (07) : 382 - 387
  • [4] Conway RW., 1967, THEORY SCHEDULING
  • [5] Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
  • [6] UNIT EXECUTION TIME SHOP PROBLEMS
    GONZALEZ, T
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 1982, 7 (01) : 57 - 66
  • [7] Graham R. L., 1979, Discrete Optimisation, P287
  • [8] LIVSHITS EM, 1972, COMPUTATIONAL MATH C, V3, P78
  • [9] Smith W., 1956, Naval Res. Logistics Q., V3, P59, DOI DOI 10.1002/NAV.3800030106
  • [10] SOME NO-WAIT SHOPS SCHEDULING PROBLEMS - COMPLEXITY ASPECT
    SRISKANDARAJAH, C
    LADET, P
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 24 (03) : 424 - 438
12