Related Studies
Akturk, M. S., Gultekin, H., Karasan, E. O., (2005) Robotic Cell Scheduling with Operational Flexibility, Discrete Applied Mathematics, 145 (3), 334-348. (pdf can be found here)
Abstract: In this paper, we study the problem of two-machine, identical parts robotic cell scheduling with operational flexibility. We assume that every part to be processed has a number of tasks to be completed in these two machines and both machines are capable of performing all of the tasks. The decision to be made includes finding the optimal robot move cycle and the optimal allocation of tasks to these two machines corresponding to this robot move cycle that jointly minimize the cycle time. We proved that 1-unit robot move cycles are not necessarily optimal with this definition of the problem any more and that according to given parameters either one of the 1-unit robot move cycles or a 2-unit robot move cycle is optimal. We proposed a new robot move cycle, which is a result of the assumption of operational flexibility. This cycle is not only simple and practical but also dominates all of the common cycles reported in the literature. Finally, we considered the change of layout and showed that the cycle time of the proposed cycle can be further reduced by a change in the layout while the cycle times of all other cycles remain the same.
Gultekin, H., Akturk, M. S., Karasan, E. O., (2005) Robotic Cell Scheduling with Tooling Constraints, European Journal of Operational Research, to appear. (pdf can be found here)
Abstract: In this study, we deal with the robotic cell scheduling problem with two machines and identical parts. In an ideal FMS, each machine is capable of performing all tasks of all parts by changing tools. However, this assumption may be unrealistic at times since the required tools are stored in the tool magazines which have limited capacity and in many practical instances the required number of tools exceeds this capacity. Consequently, we assume that some tasks can only be processed on the first machine while some others can only be processed on the second machine. Remaining tasks can be processed on both machines. The problem is to find the allocation of the remaining tasks to the machines and the optimal robot move cycle that jointly minimize the cycle time. As a solution of the problem, we prove that the optimal solution is either a 1-unit or a 2-unit robot move cycle and we present the regions of optimality. Finally, a sensitivity analysis on the results is conducted.
Gultekin, H., Akturk, M. S., Karasan, E. O., (2005) Scheduling in a Three-Machine Robotic Manufacturing Cell, Computers &Operations Research, to appear. (pdf can be found here)
Abstract: In this study, we consider a Flexible Manufacturing Cell (FMC) processing identical parts on which the loading and unloading of machines are made by a robot. The machines used in FMCs are predominantly CNC machines and these machines are flexible enough for performing several operations provided that the required tools are stored in their tool magazines. Traditional research in this area considers a flowshop type system. The current study relaxes this flowshop assumption which unnecessarily limits the number of alternatives. We propose a new robot move cycle which is a direct consequence of process and operational flexibility. We prove that this proposed cycle dominates all 2-unit robot move cycles and present the regions where the proposed cycle dominates all 1-unit cycles. We also present a worst case performance bound of using this proposed cycle instead of the optimal robot move cycle.
Gultekin,H., H., Akturk, M. S., Karasan, E. O., (2005) Scheduling in Robotic Cells: Process Flexibility and Cell Layout, International Journal of Production Research, submitted.
Abstract: The focus of this study is identical parts robotic cell scheduling problem with m-machines under the assumption of process and operational flexibility. A direct consequence of this assumption is a new robot move cycle which is overlooked in the existing literature. We prove that this new cycle dominates all classical robot move cycles considered in the literature for m=2. We also prove that changing the layout from an in-line robotic cell to a robot centered cell reduces the cycle time of the proposed cycle even further whereas the cycle times of all other robot move cycles remain the same. For the general $m$-machine case we find the regions of optimality for the proposed cycle and present a worst case performance bound for the remaining regions. Considering the number of machines as a decision variable, we also find the optimal number of machines that minimizes the cycle time of the proposed cycle.
Agnetis A., (1997) No-wait flow shop scheduling with large lot sizes.
Aneja, Y.P., Kamoun, H., (1999) Scheduling of parts and robot activities in two-machine robotic cell. Computers and Operations Research 26 297312.
Blazewicz, J., Pawlak, G.,Walter, B., (2002) Scheduling Production Tasks in a Two-Stage FMS. International Journal of Production Research 40 (17) 43414352.
Che, A., Chu, C., Levner, E., (2003) A polynomial algorithm for 2-degree cyclic robot scheduling. European Journal of Operations Research 145 3144.
Crama, Y., Van de Klundert, J., (1997) Cyclic scheduling of identical parts in a robotic cell. Operations Research 45 (6) 952965.
Crama, Y., Van de Klundert, J., (1999) Cyclic scheduling in 3-machine robotic flow shops. Journal of Scheduling 4, 3554.
Crama, Y., Kats, V., Van de Klundert, J., Levner, E., (2000) Cyclic scheduling in robotic flowshops. Annals of Operations Research 96, 97124.
Dawande, M., Sriskandarajah, C., Sethi, S., (2002) On Throughput Maximization in Constant Travel-Time Robotic Cells. Manufacturing and Service Operations Management 4 (4) 296312.
Hurink, J., Knust, S., (2001) Makespan minimization for flow-shop problems with transportation times and a single robot. Discrete Applied Mathematics 112 199216.
Hurink, J., Knust, S., (2002) A tabu search algorithm for scheduling a single robot in a job-shop environment. Discrete Applied Mathematics 119, 181203.
Kats, V., Levner, E., (2002) Cyclic scheduling in a robotic production line.
Kats, V., Levner, E., (1997) Minimizing the number of robots to meet a given cyclic schedule. Annals of Operations Research 69, 209226.
Lee, C.Y., Lei, L., Pinedo, M., (1997) Current trends in deterministic scheduling.
Logendran, R., Sriskandarajah, C., (1996) Sequencing of robot activities and parts in two-machine robotic cells. International Journal of Production Research 34, 34473463.
Hall, N.G., Kamoun, H., Sriskandarajah, C., (1997) Scheduling in robotic cells: classification, two and three machine cells. Operations Research 45 (3) 421439.
Hall, N.G., Potts, C.N., Sriskandarajah, C., (2000) Parallel machine scheduling with a common server. Discrete Applied Mathematics 102, 223243.
Hall, N.G., Kamoun, H., Sriskandarajah, C., (1998) Scheduling in robotic cells: complexity and steady state analysis. European Journal of Operations Research 109 4365.
Hall, Sriskandarajah, C., (1996) A survey of Machine Scheduling Problems with Blocking and No-Wait in Process. Operations Research 44 (3) 510525.
Han, B.T., Cook, J.S., (1998) An efficient heuristic for robot acquisition and cell formation. Annals of Operations Research 77, 229252.
Sethi, S.P., Sriskandarajah, C., Sorger, G., Blazewicz, J. Kubiak, W., (1992) Sequencing of parts and robot moves in a robotic cell. International Journal of Flexible Manufacturing Systems 4, 331358.
Sriskandarajah, C., Hall, N.G., Kamoun, H., (1998) Scheduling large robotic cells without buffers. Annals of Operations Research 76, 287321.
Sriskandarajah, C., Drobouchevitch, I.G., Sethi, S., Chandrasekaran, R., (2000) Scheduling Multiple Parts in a Robotic Cell Served by a Dual Gripper Robot, Working paper.
Drobouchevitch, I.G., Sethi, S., Sidney, J., Sriskandarajah, C., (2000a) Scheduling Dual Gripper Robotic Cell: One-Unit Cycles, Working paper.
Drobouchevitch, I.G., Sethi, S., Sidney, J., Sriskandarajah, C., (2000b) Scheduling Multiple Parts in Two-Machine Dual Gripper Robotic Cell: Heuristic Algorithm and Performance Guarantee, Working paper.
Sethi, S., Sriskandarajah, C., Sidney, J., (2001) Scheduling in Dual Gripper Robotic Cells for productivity Gains, IEEE Transactions on Robotics and Automation, 17 324341.
Kamoun, H., Hall, N.G., Sriskandarajah, C., (1999) Scheduling in robotic cells: heuristics and cell design. Operations Research 47, (6) 821835.
Hartley, J.,
Crama, Y., Kats, V., Van de Klundert, J., Levner, E., (2000) Cyclic scheduling in robotic flowshops. Annals of Operations Research 96, 97124.
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G, (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals Discrete Mathematics 5 287326.
Geismar, H.N., Dawande, M., Sethi, S., Sriskandarajah, C., (2002) Sequencing and Scheduling in Robotic Cells: A Survey. University of Texas at Dallas.
Brauner, N., Finke, G., (1999a) On the conjecture in robotic cells: new simplified proof for the three-machine case. INFOR 37 2036.
Brauner, N., Finke, G., KubiakW., (2001) Complexity of One-Cycle Robotic Flow-Shops, Working Paper, Laboratoire LEIBNIZ, Institut IMAG, Grenoble, France.
Brauner, N., Finke, G., (1997) Final Results on the One-cycle Conjecture in Robotic Cells. Internal note, Laboratoire LEIBNIZ, Institut IMAG, Grenoble, France.
Gilmore, P.C., Gomory, R.E., (1964) Sequencing in one state-variable machine: a solvable case of the travelling salesman problem. Operations Research 12 655679.
Kise, H., Shioyama, T., Ibaraki, T., (1993) Automated two machine flowshop scheduling: a solvable case. IIE Transactions 23 8087.
Stecke, K., Browne, J., (1985) Variations in flexible manufacturing systems according to the relevant types of automated material handling. Material Flow 179185.
Kiran, A.S., Krason, R.J., (1988) Automatic tooling in a flexible manufacturing system. Industrial Engineering April, 1540.
Stern, H.I., Vitner, G., (1990) Scheduling parts in a combined production-transportation work cell. Journal of the Operational Reseach Society 41 625632.
Papdimitriou, C.H., Kanellakis, P.C., (1980) Flowshop scheduling with limited temporary storage. Journal of the ACM 27 (3) 533549.
Hitomi, K., Yoshimura, M.,
King, R.E., Hodgson, T.J., Chafee, F.E., (1993) Robot task scheduling in a flexible manufacturing cell. IIE Transactions 25 (2) 8087.
Finke, G., Gueguen, C., Brauner, N., Robotic cells with buffer space, in:
Levner, E., Kogan, K., Levin, Y., (1995) Scheduling a two-machine robotic cell: a solvable case. Annals of Operations Research 57 217232.
Levner, E., Kats, V., Levit, V.E., (1997) An improved algorithm for cyclic flowshop scheduling in a robotic cell. European Journal of Operational Research 97 500508.
Kogan K., Levner, E., (1997) A polynomial algorithm for scheduling small-scale manufacturing cells served by multiple robots. Computers and Operations Research 25 (1) 5362.
Jeng, W., Lin, J., Wen, U., (1993) Algorithms for sequencing robot activities in a robot centered parllel-processor workcell. Computers and Operations Research 20 185197.
Karzanov, A.V., Livshits, E.M., (1978) Minimal quality of operators for serving a homogeneous linear technological process, Part 2. Automation and Remote Control 39 (3) 445450.
Lieberman, R.W., Turksen, I.B., (1981) Crane scheduling problems
Kats, V., Levner, E., (1998) 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 129138.
Kats, V., Levner, E., (1997) A stringly polynomial algorithm for no-wait cyclic robotic flowshop scheduling. Operations Research Letters 21 171179.
Song, W., Zabinksky, Z.B., Storch, R.L., (1993) An algorithm for scheduling a chemical processing tank line. Production Planning and Control 4 (4) 323332.
Levner, E., Vlach, M., Single machine scheduling with fuzzy precedence constraints. ISRR-97-0031F School of Information Science, Japan Institute of Science and Technology, Hokuriku, (1997).
M. Pinedo, Scheduling: Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs, New Jersey (1995).