Using Simulated Annealing for Flexible Robotic Cell Scheduling

Abstract

We focus on the scheduling problem arising in two-machine robotic cells in which sets of multiple part-types are produced. Completion time of the production depends on the robot moves as well as the part assignments and processing times of the parts. We try to find the robot move sequence, the part sequence and the allocated processing times of the parts on each machine that jointly minimize the makespan. A simulated annealing based algorithm is proposed in order to solve the problem of determining the best schedule in a two-machine cell. Experimental results show that this approach works well and can be extended for further cases.

Keywords

• Flexible manufacturing systems
• robotic cell
• multiple part-type production
• allocated processing times
• simulated annealing

References

1. Dawande, M., Geismar, N., Sethi, S.P., “Dominance of cyclic solutions and challenges in the scheduling of robotic cells”, SIAM Review, 47, 709-721, (2005).
2. Gundogdu, E., Gultekin, H., “Scheduling in two-machine robotic cells with a self-buffered robot”, IIE Transactions, 48(2): 170-191, (2016).
3. Gan, H-S., Wirth, A., Abdekhodaee, A., “A branch-and-price algorithm for the general case of scheduling paralel machines with a single server”, Computers and Operations Research, 39: 2242-2247, (2012).
4. Hasani, K., Kravchenko, S.A., Werner, F., “Block models for scheduling jobs on two parallel machines with a single server”, Computers and Operations Research, 41: 94-97, (2014).
5. Hasani, K., Kravchenko, S.A., Werner, F. “Minimising interference for scheduling two parallel machines with a single server”, International Journal of Production Research, 52(24): 7148-7158, (2014).
6. Jiang, Y., Zhang, Q., Hu, J., Dong, J., Ji, M., “Single-server parallel-machine scheduling with loading and unloading times”, Journal of Combinatorial Optimization, 30(2): 201-213, (2015).
7. Hasani, K., Kravchenko, S.A., Werner, F., “Minimizing the makespan for the two-machine scheduling problem with a single server: Two algorithms for very large instances”, Engineering Optimization, 48(1): 173-183, (2016).
8. Balin, S., “Nonidentical parallel machine scheduling using genetic algorithm”, Expert Systems with Applications, 38, 6814-6821, (2011).

9. Bilyk, A, Mönch, L., “A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines”, Journal of Intelligent Manufacturing, 23(5), 1621-1635, (2012).
10. Browne, J., Harhen, J., Shivnan, J., Production Management Systems. New York: Addison-Wesley, (1996).
11. Gultekin, H., Akturk, M.S., Karasan, O.E., “Robotic cell scheduling with tooling constraints”, European Journal of Operational Research, 174, 777-796, (2006).
12. Jolai, F., Foumani, M., Tavakoli-Moghadam, R, Fattahi, P., “Cyclic scheduling of a robotic flexible cell with load lock and swap”, Journal of Intelligent Manufacturing 23(5), 1885-1891, (2012).
13. Mansouri, S.A., Hendizadeh, S.H, Salmasi, N., “Bicriteria scheduling of a two-machine flowshop with sequence-dependent setup times”, International Journal of Advanced Manufacturing Technology, 40, 1216-1226, (2009).
14. Naderi, B., Fatemi Ghomi S.M.T., Aminnayeri, M., “A high performing metaheuristic for job shop scheduling with sequence-dependent setup times”, Applied Soft Computing, 10, 703-710, (2010).
15. Werner, F., Kravchenko, S.A., “Scheduling with multiple servers”. Automation and Remote Control. 71, 2109-2121, (2010).
16. Mor, B., Mosheiov, G., “Heuristics for scheduling problems with an unavailability constraint and position-dependent processing times”, Computers and Industrial Engineering, 62, 908-916, (2012).
17. Jiang, Y., Dong, J., Ji, M., “Preemptive scheduling on two parallel machines with a single server”, Computers and Industrial Engineering, 66, 514-518, (2013).
18. Batur, G.D., Karasan, O.E., Akturk, M.S., “Multiple part-type scheduling in flexible robotic cells”, International Journal of Production Economics, 135, 726-740, (2012).
19. Metropolis, N., Rosenbluth, A., Resenbluth, M., “Equation of state calculations by fast computing machines”, Journal of Chemical Physics, 21, 1087–1092, (1953).
20. Kirkpatrick, S., Gelatt, Jr., C.D., Vecchi, M.P., “Optimization by simulated annealing”, Science, 220, 671-680, (1983).
21. Hooda, N., Dhingra, A.K., “Flow shop scheduling using simulated annealing: A review”, International Journal of Applied Engineering Research, 2, 234-249, (2011).
22. Low, C., Yeh, J.Y., Huang K.I., “A robust simulated annealing heuristic for flow shop scheduling problems”, International Journal of Advanced Manufacturing Technology, 23, 762-767, (2004).
23. Lee, Z.J., Lin, A.W., Ying, K.C., “Scheduling jobs on dynamic parallel machines with sequence-dependent setup times”, International Journal of Advanced Manufacturing Technology, 47, 773-781, (2010).
24. Behnamian, J. Zandieh, M., Fatemi Ghomi, S.M.T., “Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm”, Expert Systems with Applications, 36, 9637-9644, (2009).
25. Zhang, R., Wu C., “A hybrid immune simulated annealing algorithm for the job shop scheduling problem”, Applied Soft Computing, 10, 79–89, (2010).