Cyclic scheduling in robotic flowshops

[en] Fully automated production cells consisting of flexible machines and a material handling robot have become commonplace in contemporary manufacturing systems. Much research on scheduling problems arising in such cells, in particular, in flowshop-like production cells has been reported recently. Although there are many differences between the models, they all explicitly incorporate the interaction between the materials handling and the classical job processing decisions, since this interaction determines the efficiency of the cell. This paper surveys cyclic scheduling problems in robotic flowshops, models for such problems, and the complexity of solving these problems, thereby bringing together several streams of research that have by and large ignored one another, and describing and establishing links with other scheduling problems and combinatorial topics.

Disciplines :

Quantitative methods in economics & management
Production, distribution & supply chain management

Author, co-author :

Crama, Yves ; Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production

Kats, Vladimir

Van de Klundert, Joris

Levner, Eugene

Language :

English

Title :

Cyclic scheduling in robotic flowshops

Publication date :

2000

Journal title :

Annals of Operations Research

ISSN :

0254-5330

eISSN :

1572-9338

Publisher :

Springer Science & Business Media B.V.

Volume :

Pages :

97-124

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 10 October 2016

Statistics

Number of views

57 (0 by ULiège)

Number of downloads

306 (0 by ULiège)

More statistics

Scopus citations^®

176

Scopus citations^®
without self-citations

160

OpenCitations

144

Bibliography

A. Agnetis, No-wait flowshop scheduling with large lot size, Annals of Operations Research 70 (1997) 415-438.
A. Agnetis, Scheduling no-wait robotic cells with two and three machines, Technical Report 21-97, Università degli studi di Roma, La Sapienza (1997).
V.S. Aizenshtat, Combining primitive cyclic processes, Doklady Academy Nauk BSSR 7(3) (1963) 148-151 (in Russian).
V.S. Aizenshtat, Multioperator cyclic processes, Doklady Academy Nauk BSSR 7(4) (1963) 224-227 (in Russian).
R. Armstrong, L. Lei and S. Gu, A bounding scheme for deriving the minimal cycle time of a single transporter N-stage process with time windows, European Journal of Operational Research 78 (1994) 130-140.
C.R. Asfahl, Robots and Manufacturing Automation (Wiley, New York, 1985).
J.J. Bartholdi, J.B. Orlin and H.D. Ratliff, Cyclic scheduling via integer programs with circular ones, Operations Research 28 (1980) 1073-1085.
J. Blazewicz and G. Finke, Scheduling with resource management in manufacturing systems, European Journal of Operational Research 76 (1994) 1-14.
N. Brauner and G. Finke, On a conjecture about robotic cells: new simplified proof for the three machine case, Journal of Information Systems and Operational Research - INFOR 37 (1999) 20-36.
N. Brauner and G. Finke, On cycles and permutations in robotic cells, Mathematical and Computer Modelling, to appear.
N. Brauner, G. Finke and W. Kubiak, A proof of the Lei and Wang claim, Technical Note, Laboratoire Leibniz, Institut IMAG, Grenoble (1997).
J. Carlier and Ph. Chrétienne, Problèmes d'Ordonnancement: Modélisation, Complexité, Algorithmes, Etudes et Recherche en Informatique (Masson, Paris, 1988).
H. Chen, C. Chu and J.-M. Proth, Cyclic scheduling of a hoist with time window constraints, Rapport de recherche Nr 2307, INRIA (1994).
C. Chu and J.-M. Proth, Single machine scheduling with chain structures precedence constraints and separation time windows, IEEE Transactions on Robotics and Automation 12(6) (1996) 835-844.
G. Cohen, D. Dubois, J.P. Quadrat and M. Viot, A linear-system-theoretic review of discrete-event processes and its use for performance evaluation in manufacturing, IEEE Transactions on Automatic Control AC30(3) (1985) 210-220.
Y. Crama, Combinatorial optimization models for production scheduling in automated manufacturing systems, European Journal of Operational Research 99 (1997) 136-153.
Y. Crama and J. Van de Klundert, Cyclic scheduling of identical parts in a robotic cell, Operations Research 45(6) (1997) 952-965.
Y. Crama and J. Van de Klundert, Cyclic scheduling in 3-machine robotic flow shops, Research memorandum RM97018, Maastricht University, Maastricht. In revision for Journal of Scheduling (1997).
Y. Crama and J. Van de Klundert, Robotic flowshop scheduling is strongly NP-complete, in: Ten Years LNMB, eds. W.K. Klein Haneveld et al. (CWI Tract, Amsterdam, 1997) pp. 277-286.
G. Finke, C. Gueguen and N. Brauner, Robotic cells with buffer space, in: ECCO IX Conference Proceedings, eds. R. O'Conner and P. Magee (Dublin City University, 1996).
P.C. Gilmore and R.E. Gomory, Sequencing a one state-variable machine: a solvable case of the traveling salesman problem, Operations Research 12 (1964) 655-679.
P.C. Gilmore, E.L. Lawler and D.B. Shmoys, Well solved special cases, in: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, eds. E.L. Lawler et al., Wiley-Interscience Series in Discrete Mathematics (Wiley, Chichester, 1985).
C.A. Glass, Y.M. Shafransky and V.A. Strusevich, Scheduling for parallel dedicated machines with a single server, CASSM R&D Paper 8, University of Greenwich, London (1995).
M. Gondran and M. Minoux, Graphs and Algorithms (Wiley-Interscience, Chichester, 1984).
N.G. Hall, H. Kamoun and C. Sriskandarajah, Scheduling in robotic cells: complexity and steady state analysis, Working Paper, College of Business, The Ohio State University (1995).
N.G. Hall, H. Kamoun and C. Sriskandarajah, Scheduling in robotic cells: classification, two and three machine cells, Operations Research 45(3) (1997) 421-439.
N.G. Hall, C.N. Potts and C. Sriskandarajah, Parallel machine scheduling with a common server, Working Paper, The Ohio State University (1995).
N.G. Hall and C. Sriskandarajah, A survey of machine scheduling problems with blocking and no-wait in process, Operations Research 44 (1996) 510-525.
C. Hanen and A. Munier, Periodic scheduling of several hoists, in: Proc. 4th International Conf. Project Management and Scheduling (1994) pp. 108-110.
C. Hanen and A. Munier, Cyclic scheduling on parallel processors: an overview, in: Scheduling Theory and its Applications, eds. Ph. Chrétienne et al. (Wiley, 1995).
M. Hartmann and J.B. Orlin, Finding minimum cost to time ratio cycles with small integer transit times, Networks 23 (1993) 567-574.
A. Hertz, Private communication (1995).
A. Hertz, Y. Mottet and Y. Rochat, On a scheduling problem in a robotized analytical system, Discrete Applied Mathematics 65 (1996) 285-316.
K.L. Hitz, Scheduling of flow shops II, Report No. LIDS-R-879, Laboratory for information and decision systems, MIT, Cambridge (1980).
I. Ioachim and F. Soumis, Schedule eficiency in a robotic production cell, International Journal of Flexible Manufacturing Systems 7 (1995) 5-26.
W.D. Jeng, J.T. Lin and U.P. Wen, Algorithms for sequencing robot activities in a robot-centered parallel-processor workcell, Computers and Operations Research 20(2) (1993) 185-197.
S.M. Johnson, Optimal two and three-stage production schedules with set up times included, Naval Research Logistics Quarterly 1 (1954) 61-68.
H. Kamoun, N.G. Hall and C. Sriskandarajah, Scheduling in robotic cells: heuristics and cell design, Working Paper, University of Toronto (1993). To appear in Operations Research.
H. Kamoun and C. Sriskandarajah, The complexity of scheduling jobs in repetitive manufacturing systems, European Journal of Operational Research 70 (1993) 350-364.
R.M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Mathematics 23 (1978) 309-311.
R.M. Karp and J.B. Orlin, Parametric shortest path algorithms with an application to cyclic staffing, Discrete Applied Mathematics 3 (1981) 37-45.
A.V. Karzanov and E.M. Livshits, Minimal quality of operators for serving a homogeneous linear technological process, Part 2, Automation and Remote Control 39(3) (1978) 445-450.
V.B. Kats, An exact optimal cyclic scheduling algorithm for multioperator service of a production line, Part 2, Automation and Remote Control 42(4) (1982) 538-543.
V. Kats and E. Levner, Polynomial algorithms for scheduling of robots, in: Intelligent Scheduling of Robots and FMS, ed. E. Levner (CTEH Press, Holon, Israel, 1996) pp. 77-100.
V. Kats and E. Levner, A strongly polynomial algorithm for no-wait cyclic robotic flowshop scheduling, Operations Research Letters 21 (1997) 171-179.
V. Kats and E. Levner, Minimizing the number of robots to meet a given schedule, Annals of Operations Research 69 (1997) 209-226.
V. Kats and E. Levner, Polynomial algorithms for cyclic scheduling of tasks on parallel processors, in: Proceedings of the 16th IASTED International Conference on Applied Informatics, Garmisch, Germany, February 23-25, 1998 (IASTED/ACTA Press, Anaheim) pp. 302-304.
V. Kats and E. Levner, Cyclic scheduling of operations for a part type in an FMS handled by a single robot: a parametric critical path approach, The International Journal of Flexible Manufacturing Systems 10 (1998) 129-138.
V. Kats, E. Levner and L. Meyzin, Multiple part cyclic hoist scheduling using a sieve method, Technical Report, Center for Technological Education, Holon, Israel (1997).
V. Kats and Z.N. Mikhailetsky, Exact solution of a cyclic scheduling problem, Automation and Remote Control 4 (1980) 187-190 (in Russian).
R.E. King, T.J. Hodgson and F.W. Chafee, Robot task scheduling in a flexible manufacturing cell, IIE Transactions 25(2) (1993) 80-87.
H. Kise, On an automated two-machine flowshop scheduling problem with infinite buffer, Journal of the Operations Research Society of Japan 34(3) (1991) 354-361.
H. Kise, T. Shioyama and T. Ibaraki, Automated two machine flowshop scheduling: a solvable case, IIE Transactions 23(1) (1991) 10-16.
J.J. van de Klundert, Scheduling problems in automated manufacturing, Dissertation 96-35, Faculty of Economics and Business Administration, Maastricht University (1996).
K. Kogan and E. Levner, A polynomial algoritm for scheduling small-scale manufacturing cells served by multiple robots, Computers and Operations Research 25(1) (1997) 53-62.
T.E. Lee and M.E. Posner, Performance measures and schedules in periodic job shops, Operations Research 45(1) (1997) 72-91.
L. Lei, Determining the optimal starting times in a cyclic schedule with a given route, Computers and Operations Research 20(8) (1993) 807-816.
L. Lei, Private communication (1995).
L. Lei, R. Armstrong and S. Gu, Minimizing the fleet size with dependent time-window and single-track constraints, Operations Research Letters 14 (1993) 91-98.
L. Lei and T.J. Wang, A proof: The cyclic hoist scheduling problem is NP-complete, Working Paper 89-16, Graduate School of Management, Rutgers University (1989).
L. Lei and T.J. Wang, The mimimum common cycle algorithm for cyclic scheduling of two hoists with time window constraints, Management Science 37(12) (1991) 1629-1639.
L. Lei and T.J. Wang, Determining optimal cyclic hoist schedules in a single-hoist electroplating line, IIE Transactions 26(2) (1994) 25-33.
E. Levner, Optimal planning of parts machining on a number of machines, Automatic Remote Control 12 (1969) 1972-1978.
E. Levner, V. Kats and V.E. Levit, An improved algorithm for cyclic flowshop scheduling in a robotic cell, European Journal of Operational Research 97 (1997) 500-508.
E. Levner, V. Kats and C. Sriskandarajah, A geometric algorithm for scheduling of robots, in: Intelligent Scheduling of Robots a and FMS, ed. E. Levner (CTEH Press, Holon, Israel, 1996) pp. 101-112.
E. Levner, K. Kogan and Y. Levin, Scheduling a two-machine robotic cell: a solvable case, Annals of Operations Research 57 (1995) 217-232.
E. Levner, K. Kogan and O. Maimon, Flowshop scheduling of robotic cells with job dependent transportation and set-up effects, Journal of the Operational Research Society 46 (1995) 1447-1455.
E. Levner and M. Vlach, Single machine scheduling with fuzzy precedence constraints, IS-RR-97-0031F, School of Information Science, Japan Institute of Science and Technology, Hokuriku (1997).
R.W. Lieberman and I.B. Turksen, Crane scheduling problems, AIIE Transactions 13(4) (1981) 304-311.
E.M. Livshits, Z.N. Mikhailetsky and Chervyakov, A scheduling problem in an automated flow line with an automated operator, Computational Mathematics and Computerized Systems 5 (1974) 151-155 (in Russian).
H. Matsuo, J.S. Shang and R.S. Sullivan, A crane scheduling problem in a computer integrated manufacturing environment, Management Science 37(5) (1991) 587-606.
S.T. McCormick, M.L. Pinedo, S. Shenker and B. Wolf, Sequencing in an assembly line with blocking to minimize cycle time, Operations Research 37(6) (1989) 925-935.
S.T. McCormick and U.S. Rao, Some complexity results in cyclic scheduling, Mathematical and Computer Modelling 20 (1994) 107-122.
W.C. Ng and J. Leung, Determining the optimal move times for a given cyclic schedule of a material handling hoist, Computers and Industrial Engingeering 32(3) (1997) 595-606.
J.B. Orlin, Minimizing the number of vehicles to meet a fixed periodic schedule: An application of periodic posets, Operations Research 30(4) (1982) 760-776.
C.H. Papadimitriou and P.C. Kanellakis, Flowshop scheduling with limited temporary storage, Journal of the ACM 27(3) (1980) 533-549.
Y.B. Park, Optimizing robot's service movement in a robot-centered FMC, Computers and Industrial Engineering 27(1-4) (1994) 47-50.
L.W. Phillips and P.S. Unger, Mathematical programming solution of a hoist scheduling program, AIIE Transactions 8(2) (1976) 219-225.
M. Pinedo, Scheduling: Theory, Algorithms and Systems (Prentice-Hall, Englewood Cliffs, NJ, 1995).
Y. Rochat, A genetic approach for solving a scheduling problem in a robotized analytical system, in: Intelligent Scheduling of Robots and FMS, ed. E. Levner (Center for Technological Education Holon, Israel, 1995) pp. 191-209.
H. Rock, The three-machine no-wait flowshop scheduling problem is NP-complete, Journal of the ACM 33 (1984) 336-345.
R. Roundy, Cyclic schedules for job-shops with identical jobs, Mathematics of Operations Research 17 (1992) 842-865.
P. Serafini and W. Ukowich, A mathematical model for periodic scheduling problems, SIAM Journal on Discrete Mathematics 2 (1989) 550-581.
S.P. Sethi, C. Sriskandarajah, G. Sorger, J. Blazewicz and W. Kubiak, Sequencing of parts and robot moves in a robotic cell, International Journal of Flexible Manufacturing Systems 4 (1992) 331-358.
G.W. Shapiro and H.L.W. Nuttle, Hoist scheduling for a PCB electroplating facility, IIE Transactions 20 (1988) 157-167.
C. Sriskandarajah, N.G. Hall, H. Kamoun and H. Wan, Scheduling large robotic cells without buffers, Annals of Operations Research 76 (1998) 287-321.
W. Song, Z.B. Zabinsky and R.L. Storch, An algorithm for scheduling a chemical processing tank line, Production Planning and Control 4(4) (1993) 323-332.
D.A. Suprunenko, V.S. Aizenshtat and A.S. Metel'skii, A multistage technological process, Doklady Academy Nauk BSSR 6(9) (1962) 541-544 (in Russian).
V.S. Tanayev, A scheduling problem for a flowshop line with a single operator, Eng.-Physics Journal 7(3) (1964) 111-114 (in Russian).
V. Timkovsky, An approximate solution of a scheduling problem in a cyclic system, Economics and Mathematical Methods 8 (1986) 171-174 (in Russian).
C. Varnier, A. Bachelu and P. Baptiste, A hoist scheduling problem application in chemical production line, in: Intelligent Scheduling of Manufacturing Systems, ed. E. Levner (Institute of Technology, Arts and Science, Holon, Israel, 1996) pp. 267-282.