Abstract
Many scheduling problems involve reasoning about tasks which may or may not actually occur, so called optional tasks. The state-of-the-art approach to modelling and solving such problems makes use of interval variables which allow a start time of \(\bot\) indicating the task does not run. In this paper we show we can model interval variables in a lazy clause generation solver, and create explaining propagators for scheduling constraints using these interval variables. Given the success of lazy clause generation on many scheduling problems, this combination appears to give a powerful new solving approach to scheduling problems with optional tasks. We demonstrate the new solving technology on well-studied flexible job-shop scheduling problems where we are able to close 36 open problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Schedule Problem
- Interval Variable
- Constraint Programming
- Constraint Satisfaction Problem
- Boolean Variable
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barták, R., Čepek, O.: Temporal networks with alternatives: Complexity and model. In: Proceedings of the Twentieth International Florida AI Research Society Conference (FLAIRS), pp. 641–646 (2007)
Beck, J.C., Fox, M.S.: Scheduling alternative activities. In: Proceedings of the National Conference on Artificial Intelligence, pp. 680–687. John Wiley & Sons, Ltd. (1999)
Behnke, D., Geiger, M.J.: Test instances for the flexible job shop scheduling problem with work centers. Research Report RR-12-01-01, Helmut-Schmidt-Universität, Hamburg, Germany (2012)
Brandimarte, P.: Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research 41(3), 157–183 (1993)
Brucker, P., Schlie, R.: Job-shop scheduling with multi-purpose machines. Computing 45(4), 369–375 (1990)
Feydy, T., Somogyi, Z., Stuckey, P.J.: Half reification and flattening. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 286–301. Springer, Heidelberg (2011)
Feydy, T., Stuckey, P.J.: Lazy clause generation reengineered. In: Gent [8], pp. 352–366
Gent, I.P. (ed.): CP 2009. LNCS, vol. 5732. Springer, Heidelberg (2009)
Hurink, J., Jurisch, B., Thole, M.: Tabu search for the job-shop scheduling problem with multi-purpose machines. Operations-Research-Spektrum 15(4), 205–215 (1994)
Jurisch, B.: Scheduling jobs in shops with multi-purpose machines. Ph.D. thesis, Universität Osnabrück (1992)
Laborie, P.: IBM ILOG CP Optimizer for detailed scheduling illustrated on three problems. In: van Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 148–162. Springer, Heidelberg (2009)
Laborie, P., Rogerie, J.: Reasoning with conditional time-intervals. In: Wilson, D.C., Lane, H.C. (eds.) Proceedings of the Twenty-First International Florida Artificial Intelligence Research Society Conference, pp. 555–560. AAAI Press (2008)
Laborie, P., Rogerie, J., Shaw, P., Vilím, P.: Reasoning with conditional time-intervals part II: An algebraical model for resources. In: Lane, H.C., Guesgen, H.W. (eds.) Proceedings of the Twenty-First International Florida Artificial Intelligence Research Society Conference, pp. 201–206. AAAI Press (2009)
Laborie, P., Rogerie, J., Shaw, P., Vilím, P., Katai, F.: Interval-based language for modeling scheduling problems: An extension to constraint programming. In: Kallrath, J. (ed.) Algebraic Modeling Systems. Applied Optimization, vol. 104, pp. 111–143. Springer, Heidelberg (2012)
Mastrolilli, M., Gambardella, L.M.: Effective neighbourhood functions for the flexible job shop problem. Journal of Scheduling 3(1), 3–20 (2000)
Moffitt, M.D., Peintner, B., Pollack, M.E.: Augmenting disjunctive temporal problems with finite-domain constraints. In: Proceedings of the National Conference on Artificial Intelligence, pp. 1187–1192. AAAI Press (2005)
Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient SAT solver. In: Proceedings of Design Automation Conference – DAC 2001, pp. 530–535. ACM, New York (2001)
Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.R.: MiniZinc: Towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007)
Ohrimenko, O., Stuckey, P.J., Codish, M.: Propagation via lazy clause generation. Constraints 14(3), 357–391 (2009)
Pacino, D., Van Hentenryck, P.: Large neighborhood search and adaptive randomized decompositions for flexible jobshop scheduling. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI 2011, pp. 1997–2002. AAAI Press (2011)
Schulte, C., Stuckey, P.J.: Efficient constraint propagation engines. ACM Transactions on Programming Languages and Systems 31(1), Article No. 2 (2008)
Schutt, A., Chu, G., Stuckey, P.J., Wallace, M.G.: Maximising the net present value for resource-constrained project scheduling. In: Beldiceanu, N., Jussien, N., Pinson, É. (eds.) CPAIOR 2012. LNCS, vol. 7298, pp. 362–378. Springer, Heidelberg (2012)
Schutt, A., Feydy, T., Stuckey, P.J.: Explaining time-table-edge-finding propagation for the cumulative resource constraint. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 234–250. Springer, Heidelberg (2013)
Schutt, A., Feydy, T., Stuckey, P.J., Wallace, M.G.: Explaining the cumulative propagator. Constraints 16(3), 250–282 (2011)
Schutt, A., Feydy, T., Stuckey, P.J., Wallace, M.G.: Solving RCPSP/max by lazy clause generation. Journal of Scheduling 16(3), 273–289 (2013)
Seipel, D., Hanus, M., Wolf, A. (eds.): INAP 2007. LNCS, vol. 5437. Springer, Heidelberg (2009)
Stuckey, P.J., de la Banda, M.G., Maher, M.J., Marriott, K., Slaney, J.K., Somogyi, Z., Wallace, M., Walsh, T.: The G12 project: Mapping solver independent models to efficient solutions. In: Gabbrielli, M., Gupta, G. (eds.) ICLP 2005. LNCS, vol. 3668, pp. 9–13. Springer, Heidelberg (2005)
Vilím, P.: Edge finding filtering algorithm for discrete cumulative resources in \({\mathcal O}(kn\log n)\). In: Gent [8], pp. 802–816
Vilím, P.: Max energy filtering algorithm for discrete cumulative resources. In: van Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 294–308. Springer, Heidelberg (2009)
Vilím, P., Barták, R., Čepek, O.: Extension of O(n logn) filtering algorithms for the unary resource constraint to optional activities. Contraints 10(4), 403–425 (2005)
Walsh, T.: Search in a small world. In: Proceedings of Artificial intelligence – IJCAI 1999, pp. 1172–1177. Morgan Kaufmann (1999)
Yuan, Y., Xu, H.: Flexible job shop scheduling using hybrid differential evolution algorithms. Computers & Industrial Engineering 65(2), 246–260 (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schutt, A., Feydy, T., Stuckey, P.J. (2013). Scheduling Optional Tasks with Explanation. In: Schulte, C. (eds) Principles and Practice of Constraint Programming. CP 2013. Lecture Notes in Computer Science, vol 8124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40627-0_47
Download citation
DOI: https://doi.org/10.1007/978-3-642-40627-0_47
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40626-3
Online ISBN: 978-3-642-40627-0
eBook Packages: Computer ScienceComputer Science (R0)