Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance. (English) Zbl 1348.90331

Summary: This paper addresses a robotic cell rescheduling problem and focuses on trade-off between the total completion time of all jobs and the disturbance of a reschedule. We first define and measure the disturbance of a reschedule as the deviation of completion time of the jobs already scheduled between the reschedule and the initial schedule. To guarantee the steady performance of the system, we consider a special case that the processing sequence of the jobs already scheduled cannot be changed. The addressed rescheduling problem is transformed into a series of deterministic local scheduling problems with the objective of minimizing the total completion time of all jobs provided that the disturbance is within a given limit. A two-phase branch and bound algorithm is developed to efficiently solve the local scheduling problems. To improve the efficiency of the search procedure, a dynamic enumeration mechanism is applied to eliminate redundant constraints. Furthermore, two search strategies are proposed to direct the search procedure toward finding an optimal solution and a near-optimal solution. Finally, computational results demonstrate the efficiency of our algorithm.


90B35 Deterministic scheduling theory in operations research
68T40 Artificial intelligence for robotics
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI


[1] Levner, E.; Kats, V.; ALP, D.; Cheng, TCE., Complexity of cyclic scheduling problems: a state-of-the-art survey, Comput Ind Eng, 59, 2, 352-361, (2010)
[2] Levner, E.; Kats, V.; Levit, V. E., An improved algorithm for cyclic flowshop scheduling in a robotic cell, Eur J Oper Res, 97, 3, 500-508, (1997) · Zbl 0919.90088
[3] Levner, E.; Kogan, K.; Levin, I., Scheduling a two-machine robotic cell: a solvable case, Ann Oper Res, 57, 1, 217-232, (1995) · Zbl 0831.90075
[4] Kogan, K.; Levner, E., A polynomial algorithm for scheduling small-scale manufacturing cells served by multiple robots, Comput Oper Res, 25, 1, 53-62, (1998) · Zbl 0907.90183
[5] Kats, V.; Levner, E., A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times, Eur J Oper Res, 209, 1, 51-56, (2011) · Zbl 1208.90067
[6] Kats, V; Levner, E., A strongly polynomial algorithm for no-wait cyclic robotic flowshop scheduling, Oper Res Lett, 21, 4, 171-179, (1997) · Zbl 0892.90101
[7] Kats, V.; Levner, E., Minimizing the number of robots to meet a given cyclic schedule, Ann Oper Res, 69, 209-226, (1997) · Zbl 0880.90075
[8] Yih, Y., Algorithm for hoist scheduling problems, Int J Prod Res, 32, 3, 501-516, (1994) · Zbl 0903.90095
[9] Chen, H.; Chu, C.; Proth, J. M., Cyclic scheduling of a hoist with time window constraints, IEEE Trans Robot Autom, 14, 1, 144-152, (1998)
[10] Chauvet, F.; Levner, E.; Meyzin, L. K.; Proth, J-M., On-line scheduling in a surface treatment system, Eur J Oper Res, 120, 2, 382-392, (2000) · Zbl 0949.90038
[11] Akturk, M. S.; Gorgulu, E., Match-up scheduling under a machine breakdown, Eur J Oper Res, 112, 1, 81-97, (1999) · Zbl 0937.90029
[12] Hall, N. G.; Potts, C. N., Rescheduling for new orders, Oper Res, 52, 3, 440-453, (2004) · Zbl 1165.90456
[13] Hall, N. G.; Potts, C. N., Rescheduling for job unavailability, Oper Res, 58, 3, 746-755, (2010) · Zbl 1231.90196
[14] Qi, X.; Bard, J. F.; Yu, G., Disruption management for machine scheduling: the case of SPT schedules, Int J Prod Econ, 103, 1, 166-184, (2006)
[15] Ballestin, F.; Leus, R., Meta-heuristics for stable scheduling on a single machine, Comput Oper Res, 35, 7, 2175-2192, (2008) · Zbl 1177.90142
[16] Yildiz, S.; Karasan, O. E.; Akturk, M. S., An analysis of cyclic scheduling problems in robot centered cells, Comput Oper Res, 39, 6, 1290-1299, (2012) · Zbl 1251.90205
[17] Fazel Zarandi, M. H.; Mosadegh, H.; Fattahi, M., Two-machine robotic cell scheduling problem with sequence-dependent setup times, Comput Oper Res, 40, 5, 1420-1434, (2012) · Zbl 1352.90037
[18] Che, A.; Hu, H.; Chabrol, M.; Gourgand, M., A polynomial algorithm for multi-robot 2-cyclic scheduling in a no-wait robotic cell, Comput Oper Res, 38, 9, 1275-1285, (2011) · Zbl 1208.90056
[19] Brauner, N., Identical part production in cyclic robotic cells: concepts, overview and open questions, Discrete Appl Math, 156, 13, 2480-2492, (2008) · Zbl 1152.90429
[20] Alcaide, D.; Chu, C.; Kats, V.; Levner, E.; Sierksma, G., Cyclic multiple-robot scheduling with time-window constraints using a critical path approach, Eur J Oper Res, 177, 1, 147-162, (2007) · Zbl 1111.90033
[21] Paul, H. J.; Bierwirth, C.; Kopfer, H., A heuristic scheduling procedure for multi-item hoist production lines, Int J Prod Econ, 105, 1, 54-69, (2007)
[22] Lei, L.; Liu, Q., Optimal cyclic scheduling of a robotic processing line with two-product and time-window constraints, INFOR, 39, 2, 185-199, (2001)
[23] Lei L, Wang TJ. A proof: the cyclic hoist scheduling problem is NP-hard (Working paper #89-0016). Rutgers University; 1989.
[24] Zhou, Z.; Che, A.; Yan, P., A mixed integer programming approach for multi-cyclic robotic flowshop scheduling with time window constraints, Appl Math Modell., 36, 8, 3621-3629, (2012) · Zbl 1252.90029
[25] Leung, J. M.Y.; Zhang, G.; Yang, X.; Mak, R.; Lam, K., Optimal cyclic multi-hoist scheduling: a mixed integer programming approach, Oper Res, 52, 6, 965-976, (2004) · Zbl 1165.90460
[26] Liu, J.; Jiang, Y.; Zhou, Z., Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution, IIE Trans (Inst Ind Eng), 34, 10, 905-914, (2002)
[27] Phillips, L. W.; Unger, P. S., Mathematical programming solution of a hoist scheduling program, AIIE Trans, 8, 2, 219-225, (1976)
[28] Che, A.; Chu, C., Cyclic hoist scheduling in large real-life electroplating lines, OR Spectrum, 29, 3, 445-470, (2007) · Zbl 1173.90400
[29] Che, A.; Zhou, Z.; Chu, C.; Chen, H., Multi-degree cyclic hoist scheduling with time window constraints, Int J Pro Res, 49, 19, 5679-5693, (2011)
[30] Lei, L.; Wang, T. J., Determining optimal cyclic hoist schedules in a single-hoist electroplating line, IIE Trans (Inst Ind Eng), 26, 2, 25-33, (1994)
[31] Ng, W. C., A branch and bound algorithm for hoist scheduling of a circuit board production line, Int J Flex Manuf Syst, 8, 1, 45-65, (1996)
[32] Sharpiro, G. W.; Nuttle, H. L., Hoist scheduling for a PCB electroplating facility, IIE Trans Inst Ind Eng, 20, 2, 157-167, (1988)
[33] Brauner, N.; Finke, G.; Lehoux-Lebacque, V.; Potts, C.; Whitehead, J., Scheduling of coupled tasks and one-machine no-wait robotic cells, Comput Oper Res, 36, 2, 301-307, (2009) · Zbl 1157.90406
[34] Crama, Y.; Van De Klundert, J., Cyclic scheduling of identical parts in a robotic cell, Oper Res, 45, 6, 952-965, (1997) · Zbl 0895.90113
[35] Hall, N. G.; Kamoun, H.; Sriskandarajah, C., Scheduling in robotic cells: complexity and steady state analysis, Eur J Oper Res, 109, 1, 43-65, (1998) · Zbl 0949.90041
[36] Dawande, M.; Geismar, H. N.; Sethi, S. P.; Sriskandarajah, C., Sequencing and scheduling in robotic cells: recent developments, J Scheduling, 8, 5, 387-426, (2005) · Zbl 1123.90020
[37] Manier, M. A.; Bloch, C., A classification for hoist scheduling problems, Int J Flex Manuf Syst, 15, 1, 37-55, (2003)
[38] Bean, J. C.; Birge, J. R.; Mittenthal, J.; Noon, C. E., Matchup scheduling with multiple resources, release dates and disruptions, Oper Res, 39, 3, 470-483, (1991) · Zbl 0742.90041
[39] Akturk, M.; Atamtuk, A.; Gurel, S., Parallel machine match-up scheduling with manufacturing cost considerations, J Sched, 13, 1, 95-110, (2010) · Zbl 1185.90064
[40] Wu, S. D.; Storer, R. H.; Pei-Chann, C., One-machine rescheduling heuristics with efficiency and stability as criteria, Comput Oper Res, 20, 1, 1-14, (1993) · Zbl 0759.90049
[41] Unal, A. T.; Uzsoy, R.; Kiran, A., Rescheduling on a single machine with part-type dependent setup times and deadlines, Ann Oper Res, 70, 0, 93-113, (1997) · Zbl 0889.90092
[42] Lamothe J, Correge M, Delmas J. A dynamic heuristic for the real time hoist scheduling problem. In: IEEE Symposium on Emerging Technologies and Factory Automation. Paris; 1995: 161-8.
[43] Zhao, C.; Fu, J.; Xu, Q., Real-time dynamic hoist scheduling for multistage material handling process under uncertainties, AIChE J, 59, 2, 465-482, (2012)
[44] Escudero, L. F.; Guignard, M.; Malik, K., A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships, Ann Oper Res, 50, 1, 219-237, (1994) · Zbl 0833.90068
[45] Gambardella, L. M.; Dorigo, M., An ant colony system hybridized with a new local search for the sequential ordering problem, INFORMS J Computing, 12, 3, 237-255, (2000) · Zbl 1040.90570
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.