Shift Design with Answer Set Programming

• Autorzy: Abseher M. , Musliu N. , Woltran S. , Gebser M. , Schaub T.

Identyfikatory

DOI

10.3233/FI-2016-1396

• Konferencja: ASPOCP 2015 : ASPOCP International Workshop on “Answer Set Programming and Other Computing Paradigms” (8: August 31, 2015: Cork, Ireland)
• Języki publikacji: EN

Abstrakty

EN

Answer Set Programming (ASP) is a powerful declarative programming paradigm that has been successfully applied to many different domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling and travel allotment. In this paper, we approach another important task, namely, the shift design problem, aiming at an alignment of a minimum number of shifts in order to meet required numbers of employees (which typically vary for different time periods) in such a way that over- and understaffing is minimized. We provide an ASP encoding of the shift design problem, which, to the best of our knowledge, has not been addressed by ASP yet. Our experimental results demonstrate that ASP is capable of improving the best known solutions to some benchmark problems. Other instances remain challenging and make the shift design problem an interesting benchmark for ASP-based optimization methods.

Słowa kluczowe

EN

logic programming; combinatorial optimization; problem solving; number theory; combinatorial analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 147, nr 1
• Strony: 1--25
• Opis fizyczny: Bibliogr. 42 poz., rys., tab.

Twórcy

autor

Abseher M.

• TU Wien, Austria

autor

Musliu N.

• TU Wien, Austria

autor

Woltran S.

• TU Wien, Austria

autor

Gebser M.

• University of Potsdam, Germany

autor

Schaub T.

• University of Potsdam, Germany
• INRIA Rennes, France

Bibliografia

• [1] Abseher M, Gebser M, Musliu N, Schaub T, Woltran S. Shift Design with Answer Set Programming. In: Inclezan D, Maratea M, editors. Proceedings of the Eighth Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP’15); 2015. Available from: https://sites.google.com/site/aspocp2015/ASPOCP2015paper6.pdf.
• [2] Abseher M, Gebser M, Musliu N, Schaub T, Woltran S. Shift Design with Answer Set Programming. In: Calimeri F, Ianni G, Truszczyński M, editors. Proceedings of the Thirteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’15). vol. 9345 of Lecture Notes in Computer Science. Springer; 2015. p. 32–39. doi: 10.1007/978-3-319-23264-5_4.
• [3] Brewka G, Eiter T, Truszczyński M. Answer Set Programming at a Glance. Communications of the ACM. 2011;54(12):92–103. doi: 10.1145/2043174.2043195.
• [4] Gebser M, Kaminski R, Kaufmann B, Schaub T. Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers; 2012. doi:10.2200/S00457ED1V01Y201211AIM019.
• [5] Soininen T, Niemelä I. Developing a Declarative Rule Language for Applications in Product Configuration. In: Gupta G, editor. Proceedings of the First International Symposium on Practical Aspects of Declarative Languages (PADL’99). vol. 1551 of Lecture Notes in Computer Science. Springer; 1999. p. 305–319. doi: 10.1007/3-540-49201-1_21.
• [6] Nogueira M, Balduccini M, Gelfond M, Watson R, Barry M. An A-Prolog Decision Support System for the Space Shuttle. In: Ramakrishnan I, editor. Proceedings of the Third International Symposium on Practical Aspects of Declarative Languages (PADL’01). vol. 1990 of Lecture Notes in Computer Science. Springer; 2001. p. 169–183. doi: 10.1007/3-540-45241-9_12.
• [7] Ricca F, Grasso G, Alviano M, Manna M, Lio V, Iiritano S, Leone N. Team-Building with Answer Set Programming in the Gioia-Tauro Seaport. Theory and Practice of Logic Programming. 2012;12(3):361–381. doi: 10.1017/S147106841100007X.
• [8] Guziolowski C, Videla S, Eduati F, Thiele S, Cokelaer T, Siegel A, Saez-Rodriguez J. Exhaustively Characterizing Feasible Logic Models of a Signaling Network Using Answer Set Programming. Bioinformatics. 2013;29(18):2320–2326. doi: 10.1093/bioinformatics/btt393.
• [9] Banbara M, Soh T, Tamura N, Inoue K, Schaub T. Answer Set Programming as a Modeling Language for Course Timetabling. Theory and Practice of Logic Programming. 2013;13(4-5):783–798. doi: 10.1017/S1471068413000495.
• [10] Dodaro C, Leone N, Nardi B, Ricca F. Allotment Problem in Travel Industry: A Solution Based on ASP. In: ten Cate B, Mileo A, editors. Proceedings of the Ninth International Conference on Web Reasoning and Rule Systems (RR’15). vol. 9209 of Lecture Notes in Computer Science. Springer; 2015. p. 77–92. doi: 10.1007/978-3-319-22002-4_7.
• [11] Van den Bergh J, Beliën J, De Bruecker P, Demeulemeester E, De Boeck L. Personnel Scheduling: A Literature Review. European Journal of Operational Research. 2013;226(3):367–385. doi: 10.1016/j.ejor.2012.11.029.
• [12] Musliu N, Schaerf A, SlanyW. Local Search for Shift Design. European Journal of Operational Research. 2004;153(1):51–64. doi: 10.1016/S0377-2217(03)00098-5.
• [13] Di Gaspero L, Gärtner J, Kortsarz G, Musliu N, Schaerf A, Slany W. The Minimum Shift Design Problem. Annals of Operations Research. 2007;155(1):79–105. doi: 10.1007/s10479-007-0221-1.
• [14] Abseher M. Solving Shift Design Problems with Answer Set Programming. Master Thesis. Technische Universität Wien; 2013. Available from: http://www.dbai.tuwien.ac.at/staff/abseher/publications/Abseher13thesis.pdf.
• [15] Crawford J, Baker A. Experimental Results on the Application of Satisfiability Algorithms to Scheduling Problems. In: Hayes-Roth B, Korf R, editors. Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI’94). AAAI Press; 1994. p. 1092–1097. Available from: http://www.aaai.org/Papers/AAAI/1994/AAAI94-168.pdf.
• [16] Alviano M, Dodaro C, Marques-Silva J, Ricca F. On the Implementation of Weak Constraints in WASP: Preliminary Report. In: Inclezan D, Maratea M, editors. Proceedings of the Seventh Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP’14); 2014. Available from: https://sites.google.com/site/aspocp2014/paper_9.pdf.
• [17] Morgado A, Heras F, Liffiton M, Planes J, Marques-Silva J. Iterative and Core-Guided MaxSAT Solving: A Survey and Assessment. Constraints. 2013;18(4):478–534. doi: 10.1007/s10601-013-9146-2.
• [18] Beer A, Gärtner J, Musliu N, Schafhauser W, Slany W. Scheduling Breaks in Shift Plans for Call Centers. In: Proceedings of the Seventh International Conference on the Practice and Theory of Automated Timetabling (PATAT’08); 2008. Available from: http://www.soft-net.at/_attach/Publish/Publications/SNA34.pdf.
• [19] Beer A, Gärtner J, Musliu N, Schafhauser W, Slany W. An AI-Based Break-Scheduling System for Supervisory Personnel. IEEE Intelligent Systems. 2010;25(2):60–73. doi: 10.1109/MIS.2010.40.
• [20] Di Gaspero L, Gärtner J, Musliu N, Schaerf A, Schafhauser W, Slany W. A Hybrid LS-CP Solver for the Shifts and Breaks Design Problem. In: Blesa M, Blum C, Raidl G, Roli A, Sampels M, editors. Proceedings of the Seventh International Workshop on Hybrid Metaheuristics (HM’10). vol. 6373 of Lecture Notes in Computer Science. Springer; 2010. p. 46–61. doi: 10.1007/978-3-642-16054-7_4.
• [21] Widl M, Musliu N. The Break Scheduling Problem: Complexity Results and Practical Algorithms. Memetic Computing. 2014;6(2):97–112. doi: 10.1007/s12293-014-0131-0.
• [22] Di Gaspero L, Gärtner J, Musliu N, Schaerf A, Schafhauser W, Slany W. Automated Shift Design and Break Scheduling. In: Uyar S, Őzcan E, Urquhart N, editors. Automated Scheduling and Planning: From Theory to Practice. vol. 505 of Studies in Computational Intelligence. Springer; 2013. p. 109–127. doi: 10.1007/978-3-642-39304-4_5.
• [23] Dantzig G. A Comment on Eddie’s “Traffic delays at toll booths”. Operations Research. 1954;2(3):339–341. doi: 10.1287/opre.2.3.339.
• [24] Aykin T. A Comparative Evaluation of Modeling Approaches to the Labor Shift Scheduling Problem. European Journal of Operational Research. 2000;125(2):381–397. doi: 10.1016/S0377-2217(99)00413-0.
• [25] Bechtold S, Jacobs L. Implicit Modeling of Flexible Break Assignments in Optimal Shift Scheduling. Management Science. 1990;36(11):1339–1351. doi: 10.1287/mnsc.36.11.1339.
• [26] Rekik M, Cordeau J, Soumis F. Implicit Shift Scheduling with Multiple Breaks and Work Stretch Duration Restrictions. Journal of Scheduling. 2010;13(1):49–75. doi: 10.1007/s10951-009-0114-z.
• [27] Thompson G. Improved Implicit Modeling of the Labor Shift Scheduling Problem. Management Science. 1995;41(4):595–607. doi: 10.1287/mnsc.41.4.595.
• [28] Quimper C, Rousseau L. A Large Neighbourhood Search Approach to the Multi-Activity Shift Scheduling Problem. Journal of Heuristics. 2010;16(3):373–391. doi: 10.1007/s10732-009-9106-6.
• [29] Tellier P, White G. Generating Personnel Schedules in an Industrial Setting Using a Tabu Search Algorithm. In: Burke E, Rudová H, editors. Proceedings of the Sixth International Conference on the Practice and Theory of Automated Timetabling (PATAT’06). Masaryk University Brno; 2006. p. 293–302. Available from: http://patat06.muni.cz/doc/PATAT_2006_Proceedings.pdf.
• [30] Simons P, Niemelä I, Soininen T. Extending and Implementing the Stable Model Semantics. Artificial Intelligence. 2002;138(1-2):181–234. doi: 10.1016/S0004-3702(02)00187-X.
• [31] Leone N, Pfeifer G, Faber W, Eiter T, Gottlob G, Perri S, Scarcello F. The DLV System for Knowledge Representation and Reasoning. ACM Transactions on Computational Logic. 2006;7(3):499–562. doi: 10.1145/1149114.1149117.
• [32] Faber W, Leone N, Perri S. The Intelligent Grounder of DLV. In: Erdem E, Lee J, Lierler Y, Pearce D, editors. Correct Reasoning: Essays on Logic-Based AI in Honour of Vladimir Lifschitz. vol. 7265 of Lecture Notes in Computer Science. Springer; 2012. p. 247–264. doi: 10.1007/978-3-642-30743-0_17.
• [33] Gebser M, Kaminski R, Schaub T. Grounding Recursive Aggregates: Preliminary Report. In: Denecker M, Janhunen T, editors. Proceedings of the Third Workshop on Grounding, Transforming, and Modularizing Theories with Variables (GTTV’15); 2015. Available from: http://arxiv.org/abs/1603.03884.
• [34] Tamura N, Taga A, Kitagawa S, Banbara M. Compiling Finite Linear CSP into SAT. Constraints. 2009;14(2):254–272. doi: 10.1007/s10601-008-9061-0.
• [35] Gebser M, Kaminski R, Kaufmann B, Romero J, Schaub T. Progress in Clasp Series 3. In: Calimeri F, Ianni G, Truszczyński M, editors. Proceedings of the Thirteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’15). vol. 9345 of Lecture Notes in Computer Science. Springer; 2015. p. 368–383. doi: 10.1007/978-3-319-23264-5_31.
• [36] Alviano M, Dodaro C, Faber W, Leone N, Ricca F. WASP: A Native ASP Solver Based on Constraint Learning. In: Cabalar P, Son T, editors. Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13). vol. 8148 of Lecture Notes in Computer Science. Springer; 2013. p. 54–66. doi: 10.1007/978-3-642-40564-8_6.
• [37] Gebser M, Kaminski R, Kaufmann B, Schaub T. Multi-Criteria Optimization in Answer Set Programming. In: Gallagher J, Gelfond M, editors. Technical Communications of the Twenty-seventh International Conference on Logic Programming (ICLP’11). vol. 11 of Leibniz International Proceedings in Informatics. Dagstuhl Publishing; 2011. p. 1–10. doi: 10.4230/LIPIcs.ICLP.2011.1.
• [38] Biere A, Heule M, van Maaren H, Walsh T. Handbook of Satisfiability. vol. 185 of Frontiers in Artificial Intelligence and Applications. IOS Press; 2009. Available from: http://ebooks.iospress.nl/volume/handbook-of-satisfiability.
• [39] Andres B, Kaufmann B, Matheis O, Schaub T. Unsatisfiability-Based Optimization in Clasp. In: Dovier A, Santos Costa V, editors. Technical Communications of the Twenty-eighth International Conference on Logic Programming (ICLP’12). vol. 17 of Leibniz International Proceedings in Informatics. Dagstuhl Publishing; 2012. p. 212–221. doi: 10.4230/LIPIcs.ICLP.2012.211.
• [40] Marques-Silva J, Planes J. On Using Unsatisfiability for Solving Maximum Satisfiability. Computing Research Repository. 2007;abs/0712.1097. Available from: http://arxiv.org/abs/0712.1097.
• [41] Musliu N. Intelligent Search Methods for Workforce Scheduling: New Ideas and Practical Applications. PhD Thesis. Technische Universität Wien; 2001. Available from: http://www.dbai.tuwien.ac.at/staff/musliu/Diss.pdf.
• [42] Kocabas D. Exact Methods for Shift Design and Break Scheduling. Master Thesis. Technische Universität Wien; 2015. Available from: http://www.dbai.tuwien.ac.at/staff/musliu/KocabasDenizThesis.pdf.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).