Makespan minimization for flow-shop problems with transportation times and a single robot

被引：68
作者：
Hurink, J
Knust, S [1 ]
机构：
[1] Univ Osnabruck, Fachbereich Math Informat, D-49069 Osnabruck, Germany
[2] Univ Twente, Fac Math Sci, NL-7500 AE Enschede, Netherlands
来源：
DISCRETE APPLIED MATHEMATICS | 2001年 / 112卷 / 1-3期
关键词：
flow shop; transportation times; robot; complexity results;
D O I：
10.1016/S0166-218X(00)00316-4
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
in a flow-shop problem with transportation times and a single robot n jobs consisting of m operations have to be processed in the same order on m machines. Additionally, transportation times are considered if a job changes from one machine to another. We assume that unlimited buffer space exists between the machines and all transportations have to be done by a single robot. The objective is to determine a feasible schedule with minimal makespan. New complexity results are derived for special cases where the processing or transportation times are constant values. Some of these may also be interpreted as new results for special cases of the classical 3-machine flow-shop F3\\C-max with constant processing times at certain stages. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：199 / 216
页数：18
相关论文
共 16 条
  • [1] Cyclic scheduling of identical parts in a robotic cell
    Crama, Y
    Van de Klundert, J
    [J]. OPERATIONS RESEARCH, 1997, 45 (06) : 952 - 965
  • [2] CRAMA Y, 1997, IN PRESS ANN OPER RE
  • [3] FINKE G, 1996, C P ECCO, V9
  • [4] Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
  • [5] Graham R. L., 1979, Discrete Optimisation, P287
  • [6] Scheduling in robotic cells: Classification, two and three machine cells
    Hall, NG
    Kamoun, H
    Sriskandarajah, C
    [J]. OPERATIONS RESEARCH, 1997, 45 (03) : 421 - 439
  • [7] Johnson Selmer Martin., 1954, NAV RES LOG, V1, P61, DOI [10.1002/nav.3800010110, DOI 10.1002/NAV.3800010110, 10.1002/(ISSN)1931-9193]
  • [8] AUTOMATED 2-MACHINE FLOWSHOP SCHEDULING - A SOLVABLE CASE
    KISE, H
    SHIOYAMA, T
    IBARAKI, T
    [J]. IIE TRANSACTIONS, 1991, 23 (01) : 10 - 16
  • [9] ON AN AUTOMATED 2-MACHINE FLOWSHOP SCHEDULING PROBLEM WITH INFINITE BUFFER
    KISE, H
    [J]. JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 1991, 34 (03) : 354 - 361
  • [10] Lenstra, 1977, ANN DISCRETE MATH, V1, P343, DOI DOI 10.1016/S0167-5060(08)70743-X
12