{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T07:57:24Z","timestamp":1783411044867,"version":"3.54.6"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The cyclic hoist scheduling problem (CHSP) is a well-studied optimisation problem due to its importance in industry. Despite the wide range of solving techniques applied to the CHSP and its variants, the models have remained complicated and inflexible, or have failed to scale up with larger problem instances. This article re-examines modelling of the CHSP and proposes a new simple, flexible constraint programming formulation. We compare current state-of-the-art solving technologies on this formulation, and show that modelling in a high-level constraint language, MiniZinc, leads to both a simple, generic model and to computational results that outperform the state of the art. We further demonstrate that combining integer programming and lazy clause generation, using the multiple cores of modern processors, has potential to improve over either solving approach alone.<\/jats:p>","DOI":"10.1007\/s10601-020-09316-z","type":"journal-article","created":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T05:09:54Z","timestamp":1604898594000},"page":"319-337","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A new constraint programming model and solving for the cyclic hoist scheduling problem"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7326-8110","authenticated-orcid":false,"given":"Mark","family":"Wallace","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1814-3515","authenticated-orcid":false,"given":"Neil","family":"Yorke-Smith","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,11,9]]},"reference":[{"key":"9316_CR1","doi-asserted-by":"crossref","unstructured":"Baptiste, P., Legeard, B.,  Varnier, C. (1992). Hoist scheduling problem: an approach based on constraint logic programming. In Proc. of ICRA\u201992 (pp. 1139\u20131144).","DOI":"10.1109\/ROBOT.1992.220195"},{"key":"9316_CR2","doi-asserted-by":"crossref","unstructured":"Belov, G., Stuckey, P.J., Tack, G.,  Wallace, M. (2016). Improved linearization of constraint programming models. In Proc. of CP\u201916 (pp. 49\u201365).","DOI":"10.1007\/978-3-319-44953-1_4"},{"issue":"1","key":"9316_CR3","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.ejor.2016.08.041","volume":"258","author":"N Boysen","year":"2017","unstructured":"Boysen, N., Briskorn, D.,  Meisel, F. (2017). A generalized classification scheme for crane scheduling with interference. European Journal of Operational Research, 258(1), 343\u2013357.","journal-title":"European Journal of Operational Research"},{"key":"9316_CR4","unstructured":"Carle, M.A. (2012). Using more processors does not necessarily lead to reduced run times on CPLEX. http:\/\/www.thequestforoptimality.com\/using-more-processors-does-not-necessarily-lead-to-reduced-run-times-on-cplex\/. accessed: 2019-11-21."},{"issue":"1","key":"9316_CR5","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TASE.2013.2254713","volume":"11","author":"A Che","year":"2014","unstructured":"Che, A., Lei, W., Feng, J.,  Chu, C. (2014). An improved mixed integer programming approach for multi-hoist cyclic scheduling problem. IEEE Transaction Automation Science and Engineering, 11(1), 302\u2013309.","journal-title":"IEEE Transaction Automation Science and Engineering"},{"issue":"3","key":"9316_CR6","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1016\/j.cie.2013.03.013","volume":"65","author":"S Chtourou","year":"2013","unstructured":"Chtourou, S., Manier, M.,  Loukil, T. (2013). A hybrid algorithm for the cyclic hoist scheduling problem with two transportation resources. Computers & Industrial Engineering, 65(3), 426\u2013437.","journal-title":"Computers & Industrial Engineering"},{"key":"9316_CR7","unstructured":"Feng, J. (2017). Mod\u00e9lisation et optimisation des Hoist Scheduling Problems. Ph.D. thesis universit\u00e9 Paris-Saclay \/ Northwestern Polytechnical University (China)."},{"key":"9316_CR8","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.cie.2018.04.046","volume":"120","author":"J Feng","year":"2018","unstructured":"Feng, J., Chu, C.,  Che, A. (2018). Cyclic jobshop hoist scheduling with multi-capacity re-entrant tanks and time-window constraints. Computers & Industrial Engineering, 120, 382\u2013391.","journal-title":"Computers & Industrial Engineering"},{"key":"9316_CR9","unstructured":"IBM Support. (2018). Effects of multithread execution in CPLEX Optimization Studio models. https:\/\/www.ibm.com\/support\/pages\/effects-multithread-execution-cplex-optimization-studio-models. accessed: 2019-11-21."},{"key":"9316_CR10","doi-asserted-by":"crossref","unstructured":"Jonker, T., Duinkerken, M.B., Yorke-Smith, N., de Waal, A.,  Negenborn, R.R. (2019). Coordinated optimization of equipment operations in a container terminal. Flexible Services and Manufacturing Journal.","DOI":"10.1007\/s10696-019-09366-3"},{"key":"9316_CR11","doi-asserted-by":"crossref","unstructured":"Kizilay, D., Eliiyi, D.T.,  Hentenryck, P.V. (2018). Constraint and mathematical programming models for integrated port container terminal operations. In Proc. of CPAIOR\u201918 (pp. 344\u2013360).","DOI":"10.1007\/978-3-319-93031-2_25"},{"issue":"6","key":"9316_CR12","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1287\/opre.1040.0144","volume":"52","author":"JM Leung","year":"2004","unstructured":"Leung, J.M., Zhang, G., Yang, X., Mak, R.,  Lam, K. (2004). Optimal cyclic multi-hoist scheduling: a mixed integer programming approach. Operations Research, 52(6), 965\u2013976.","journal-title":"Operations Research"},{"issue":"3-4","key":"9316_CR13","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0360-8352(97)00254-4","volume":"33","author":"JM Lim","year":"1997","unstructured":"Lim, J.M. (1997). A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line. Computers & Industrial Engineering, 33(3-4), 789\u2013792.","journal-title":"Computers & Industrial Engineering"},{"key":"9316_CR14","doi-asserted-by":"crossref","unstructured":"Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J.,  Tack, G. (2007). Minizinc: Towards a standard CP modelling language. In Proc. of CP\u201907 (pp. 529\u2013543).","DOI":"10.1007\/978-3-540-74970-7_38"},{"key":"9316_CR15","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.cor.2014.03.005","volume":"48","author":"B Peterson","year":"2014","unstructured":"Peterson, B., Harjunkoski, I., Hoda, S.,  Hooker, J.N. (2014). Scheduling multiple factory cranes on a common track. Computers & OR, 48, 102\u2013112.","journal-title":"Computers & OR"},{"issue":"2","key":"9316_CR16","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1080\/05695557608975070","volume":"8","author":"LW Phillips","year":"1976","unstructured":"Phillips, L.W., & Unger, P.S. (1976). Mathematical programming solution of a hoist scheduling program. AIIE Transactions, 8(2), 219\u2013225.","journal-title":"AIIE Transactions"},{"issue":"1-4","key":"9316_CR17","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1023\/A:1021101321339","volume":"115","author":"D Riera","year":"2002","unstructured":"Riera, D., & Yorke-Smith, N. (2002). An improved hybrid model for the generic hoist scheduling problem. Annals of Operations Research, 115(1-4), 173\u2013191.","journal-title":"Annals of Operations Research"},{"key":"9316_CR18","unstructured":"Rodos\u0307ek, R., & Wallace, M. (1998). A generic model and hybrid algorithm for hoist scheduling problems. In Proc. of CP\u201998. pp. 385\u2013399."},{"key":"9316_CR19","doi-asserted-by":"crossref","unstructured":"Schutt, A., Feydy, T.,  Stuckey, P.J. (2013). Explaining time-table-edge-finding propagation for the cumulative resource constraint. In Proc. of CPAIOR\u201913. pp. 234\u2013250.","DOI":"10.1007\/978-3-642-38171-3_16"},{"issue":"4","key":"9316_CR20","first-page":"309","volume":"35","author":"C Varnier","year":"1997","unstructured":"Varnier, C., Bachelu, A.,  Baptiste, P. (1997). Resolution of the cyclic multi-hoists scheduling problem with overlapping partitions. INFOR: Information Systems and Operational Research, 35(4), 309\u2013324.","journal-title":"INFOR: Information Systems and Operational Research"},{"issue":"22","key":"9316_CR21","doi-asserted-by":"publisher","first-page":"6403","DOI":"10.1080\/00207543.2011.645953","volume":"50","author":"P Yan","year":"2012","unstructured":"Yan, P., Che, A., Yang, N.,  Chu, C. (2012). A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem. International Journal of Production Research, 50(22), 6403\u20136418.","journal-title":"International Journal of Production Research"},{"issue":"21","key":"9316_CR22","doi-asserted-by":"publisher","first-page":"6461","DOI":"10.1080\/00207540903225205","volume":"48","author":"P Yan","year":"2010","unstructured":"Yan, P., Chu, C., Yang, N.,  Che, A. (2010). A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with flexible processing times. International Journal of Production Research, 48(21), 6461\u20136480.","journal-title":"International Journal of Production Research"},{"key":"9316_CR23","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.cor.2016.06.011","volume":"76","author":"P Yan","year":"2016","unstructured":"Yan, P., Wang, G., Che, A.,  Li, Y. (2016). Hybrid discrete differential evolution algorithm for biobjective cyclic hoist scheduling with re-entrance. Computers & OR, 76, 155\u2013166.","journal-title":"Computers & OR"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-020-09316-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-020-09316-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-020-09316-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T23:58:55Z","timestamp":1610582335000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-020-09316-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,9]]},"references-count":23,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["9316"],"URL":"https:\/\/doi.org\/10.1007\/s10601-020-09316-z","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,9]]},"assertion":[{"value":"15 October 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}