Flow Shop Scheduling Problems Under Machine–Dependent Precedence Constraints

被引：0
|
作者：
A.A. Gladky
Y.M. Shafransky
V.A. Strusevich
机构：
[1] Institute of Engineering Cybernetics,National Academy of Sciences of Belarus
[2] University of Greenwich,School of Computing and Mathematical Sciences
来源：
Journal of Combinatorial Optimization | 2004年 / 8卷
关键词：
flow shop; precedence constraints; complexity; polynomial-time algorithm;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.
引用
收藏
页码：13 / 28
页数：15
相关论文
共 50 条
  • [1] Flow shop scheduling problems under machine-dependent precedence constraints
    Gladky, AA
    Shafransky, YM
    Strusevich, VA
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8 (01) : 13 - 28
  • [2] Shop scheduling problems under precedence constraints
    V.A. Strusevich
    Annals of Operations Research, 1997, 69 : 351 - 377
  • [3] Shop scheduling problems under precedence constraints
    Strusevich, VA
    ANNALS OF OPERATIONS RESEARCH, 1997, 69 (0) : 351 - 377
  • [4] Scheduling a flow shop to minimize the maximal lateness under arbitrary precedence constraints
    Jozefowska, J
    Zimniak, A
    INTERFACES IN COMPUTER SCIENCE AND OPERATIONS RESEARCH: ADVANCES IN METAHEURISTICS, OPTIMIZATION, AND STOCHASTIC MODELING TECHNOLOGIES, 1997, : 383 - 403
  • [5] Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints
    Zhao, Chuanli
    Tang, Hengyong
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2012, 136 (01) : 131 - 136
  • [6] Flexible job-shop scheduling problems with 'AND'/'OR' precedence constraints
    Lee, Sanghyup
    Moon, Ilkyeong
    Bae, Hyerim
    Kim, Jion
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2012, 50 (07) : 1979 - 2001
  • [7] Reduction of job-shop problems to flow-shop problems with precedence constraints
    Guinet, A
    Legrand, M
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 109 (01) : 96 - 110
  • [8] Approximation results for flow shop scheduling problems with machine availability constraints
    Kubzin, Mikhail A.
    Potts, Chris N.
    Strusevich, Vitaly A.
    COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (02) : 379 - 390
  • [9] Open-Shop Scheduling for Unit Jobs Under Precedence Constraints
    Zhang, An
    Chen, Yong
    Goebel, Randy
    Lin, Guohui
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2018), 2018, 11346 : 329 - 340
  • [10] Open-shop scheduling for unit jobs under precedence constraints
    Chen, Yong
    Goebel, Randy
    Lin, Guohui
    Su, Bing
    Zhang, An
    THEORETICAL COMPUTER SCIENCE, 2020, 803 : 144 - 151
12345