Abstract
This paper deals with the problem of scheduling feeding tasks of a single mobile robot which has capability of supplying parts to feeders on production lines. The performance criterion is to minimize the total traveling time of the robot and the total tardiness of the feeding tasks being scheduled, simultaneously. In operation, the feeders have to be replenished a number of times so as to maintain the manufacture of products during a planning horizon. A method based on predefined characteristics of the feeders is presented to generate dynamic time windows of the feeding tasks which are dependent on starting times of previous replenishment. A heuristic based on genetic algorithm which could be used to produce schedules in online production mode is proposed to quickly obtain efficient solutions. Several numerical examples are conducted to demonstrate results of the proposed approach.
Chapter PDF
Similar content being viewed by others
References
Bocewicz, G., Bach, I., Wójcik, R.: Production Flow Prototyping subject to Imprecise Activity Specification. Kybernetes 38, 1298–1316 (2009)
Choi, I.C., Kim, S.I., Kim, H.S.: A Genetic Algorithm with a Mixed Region Search for the Asymmetric Traveling Salesman Problem. Comput. Oper. Res. 30, 773–786 (2003)
Crama, Y., Kats, V., van de Klundert, J., Levner, E.: Cyclic Scheduling in Robotic Flowshops. Ann. Oper. Res. 96, 97–124 (2000)
Dang, Q.-V., Nielsen, I.E., Bocewicz, G.: A Genetic Algorithm-Based Heuristic for Part-Feeding Mobile Robot Scheduling Problem. In: Rodríguez, J.M.C., Pérez, J.B., Golinska, P., Giroux, S., Corchuelo, R. (eds.) Trends in PAAMS. AISC, vol. 157, pp. 85–92. Springer, Heidelberg (2012)
Dang, Q.V., Nielsen, I., Steger-Jensen, K., Madsen, O.: Scheduling a Single Mobile Robot for Part-feeding Tasks of Production Lines. In: J. Intell. Manuf. (2012) (accepted)
Gen, M., Lin, L.: Network Models and Optimization. Springer, London (2008)
Germs, R., Goldengorin, B., Turkensteen, M.: Lower Tolerance-Based Branch and Bound Algorithms for the ATSP. Comput. Oper. Res. 39, 291–298 (2012)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, New York (1989)
Hurink, J., Knust, S.: A TabuSearch Algorithm for Scheduling a Single Robot in a Job-shop Environment. Discrete Appl. Math. 119, 181–203 (2002)
Liu, F., Zeng, G.: Study of Genetic Algorithm with Reinforcement Learning to Solve the TSP. Expert Syst. Appl. 36, 6995–7001 (2009)
Maimon, O., Braha, D., Seth, V.: A Neural Network Approach for a Robot Task Sequencing Problem. Artif. Intell. Eng. 14, 175–189 (2000)
Moon, C., Kim, J., Choi, G., Seo, Y.: An Efficient Genetic Algorithm for the Traveling Salesman Problem with Precedence Constraints. Eur. J. Oper. Res. 140, 606–617 (2002)
Snyder, L.V., Daskin, M.S.: A Random-Key Genetic Algorithm for the Generalized Traveling Salesman Problem. Eur. J. Oper. Res. 174, 38–53 (2006)
Xing, L.N., Chen, Y.W., Yang, K.W., Hou, F., et al.: A Hybrid Approach Combining an Improved Genetic Algorithm and Optimization Strategies for the Asymmetric Traveling Salesman Problem. Eng. Appl. Artif. Intell. 21, 1370–1380 (2008)
Zacharia, P.T., Aspragathos, N.A.: Optimal Robot Task Scheduling Based on Genetic Algorithms. Robot Comput. Integrated Manuf. 21, 67–79 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 IFIP International Federation for Information Processing
About this paper
Cite this paper
Dang, QV., Nielsen, I., Steger-Jensen, K. (2013). Multi-objective Genetic Algorithm for Real-World Mobile Robot Scheduling Problem. In: Emmanouilidis, C., Taisch, M., Kiritsis, D. (eds) Advances in Production Management Systems. Competitive Manufacturing for Innovative Products and Services. APMS 2012. IFIP Advances in Information and Communication Technology, vol 397. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40352-1_65
Download citation
DOI: https://doi.org/10.1007/978-3-642-40352-1_65
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40351-4
Online ISBN: 978-3-642-40352-1
eBook Packages: Computer ScienceComputer Science (R0)