乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T06:37:26Z","timestamp":1720766246782},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,2,24]],"date-time":"2020-02-24T00:00:00Z","timestamp":1582502400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,24]],"date-time":"2020-02-24T00:00:00Z","timestamp":1582502400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Konrad-Zuse-Zentrum f\u00fcr Informationstechnik"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2020,4]]},"abstract":"Abstract<\/jats:title>In this paper, we study event-based mixed-integer programming (MIP) formulations for the resource-constrained project scheduling problem (RCPSP) that represent an alternative to the more common time-indexed model (DDT) (Pritsker et al. in Manag Sci 16(1):93\u2013108, 1969; Christofides et al. in Eur J Oper Res 29(3):262\u2013273, 1987) for the case when the scheduling horizon is large. In contrast to time-indexed models, the size of event-based models does not depend on the time horizon. For two event-based models OOE and SEE introduced by Kon\u00e9 et al.\u00a0(Comput Oper Res 38(1):3\u201313, 2011), we first present new valid inequalities that strengthen the original formulation. Furthermore, we state a new event-based model, the Interval Event-Based Model<\/jats:italic> (IEE), and deduce natural linear transformations between all three models. Those transformations yield the strict domination order

$$IEE \\succ SEE \\succ OOE$$<\/jats:tex-math>I<\/mml:mi>E<\/mml:mi>E<\/mml:mi>\u227b<\/mml:mo>S<\/mml:mi>E<\/mml:mi>E<\/mml:mi>\u227b<\/mml:mo>O<\/mml:mi>O<\/mml:mi>E<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> for their respective linear programming relaxations, meaning that the new IEE model has the strongest linear relaxation among all known event-based models. In addition, we show that DDT can be retrieved from IEE by subsequent expansion and projection of the underlying solution space. This yields a unified polyhedral view on a complete branch of MIP models for the RCPSP. Finally, we also compare the computational performance between all models on common test instances of the PSPLIB (Kolisch and Sprecher in Eur J Oper Res 96(1):205\u2013216, 1997).<\/jats:p>","DOI":"10.1007\/s10951-020-00647-6","type":"journal-article","created":{"date-parts":[[2020,2,24]],"date-time":"2020-02-24T21:04:17Z","timestamp":1582578257000},"page":"233-251","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A polyhedral study of event-based models for the resource-constrained project scheduling problem"],"prefix":"10.1007","volume":"23","author":[{"given":"Alexander","family":"Tesch","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,24]]},"reference":[{"issue":"2","key":"647_CR1","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.orl.2017.02.001","volume":"45","author":"C Artigues","year":"2017","unstructured":"Artigues, C. (2017). On the strength of time-indexed formulations for the resource-constrained project scheduling problem. Operations Research Letters, 45(2), 154\u2013159.","journal-title":"Operations Research Letters"},{"key":"647_CR2","volume-title":"Resource-constrained project scheduling: models, algorithms, extensions and applications","author":"C Artigues","year":"2013","unstructured":"Artigues, C., Demassey, S., & Neron, E. (2013). Resource-constrained project scheduling: models, algorithms, extensions and applications. Hoboken: Wiley."},{"issue":"2","key":"647_CR3","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0377-2217(02)00758-0","volume":"149","author":"C Artigues","year":"2003","unstructured":"Artigues, C., Michelon, P., & Reusser, S. (2003). Insertion techniques for static and dynamic resource-constrained project scheduling. European Journal of Operational Research, 149(2), 249\u2013267.","journal-title":"European Journal of Operational Research"},{"key":"647_CR4","volume-title":"Constraint-based scheduling: Applying constraint programming to scheduling problems","author":"P Baptiste","year":"2012","unstructured":"Baptiste, P., Le Pape, C., & Nuijten, W. (2012). Constraint-based scheduling: Applying constraint programming to scheduling problems (Vol. 39). Berlin: Springer."},{"issue":"1\u20132","key":"647_CR5","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/s10696-011-9127-y","volume":"25","author":"L Bianco","year":"2013","unstructured":"Bianco, L., & Caramia, M. (2013). A new formulation for the project scheduling problem under limited resources. Flexible Services and Manufacturing Journal, 25(1\u20132), 6\u201324.","journal-title":"Flexible Services and Manufacturing Journal"},{"issue":"1","key":"647_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0377-2217(98)00204-5","volume":"112","author":"P Brucker","year":"1999","unstructured":"Brucker, P., Drexl, A., M\u00f6hring, R., Neumann, K., & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1), 3\u201341.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"647_CR7","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/S0377-2217(99)00489-0","volume":"127","author":"P Brucker","year":"2000","unstructured":"Brucker, P., & Knust, S. (2000). A linear programming and constraint propagation-based lower bound for the RCPSP. European Journal of Operational Research, 127(2), 355\u2013362.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"647_CR8","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0377-2217(97)00335-4","volume":"107","author":"P Brucker","year":"1998","unstructured":"Brucker, P., Knust, S., Schoo, A., & Thiele, O. (1998). A branch and bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 107(2), 272\u2013288.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"647_CR9","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1016\/j.ejor.2009.04.011","volume":"201","author":"B Cardoen","year":"2010","unstructured":"Cardoen, B., Demeulemeester, E., & Beli\u00ebn, J. (2010). Operating room planning and scheduling: A literature review. European Journal of Operational Research, 201(3), 921\u2013932.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"647_CR10","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/S0377-2217(02)00763-4","volume":"149","author":"J Carlier","year":"2003","unstructured":"Carlier, J., & N\u00e9ron, E. (2003). On linear lower bounds for the resource constrained project scheduling problem. European Journal of Operational Research, 149(2), 314\u2013324.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"647_CR11","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/0377-2217(87)90240-2","volume":"29","author":"N Christofides","year":"1987","unstructured":"Christofides, N., Alvarez-Val\u00e9ds, R., & Tamarit, J. M. (1987). Project scheduling with resource constraints: A branch and bound approach. European Journal of Operational Research, 29(3), 262\u2013273.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"647_CR12","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/S0377-2217(97)00305-6","volume":"111","author":"B De Reyck","year":"1998","unstructured":"De Reyck, B., & Herroelen, W. (1998). A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research, 111(1), 152\u2013174.","journal-title":"European Journal of Operational Research"},{"issue":"11","key":"647_CR13","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1287\/mnsc.43.11.1485","volume":"43","author":"EL Demeulemeester","year":"1997","unstructured":"Demeulemeester, E. L., & Herroelen, W. S. (1997). New benchmark results for the resource-constrained project scheduling problem. Management Science, 43(11), 1485\u20131492.","journal-title":"Management Science"},{"issue":"10","key":"647_CR14","doi-asserted-by":"publisher","first-page":"1365","DOI":"10.1287\/mnsc.46.10.1365.12272","volume":"46","author":"U Dorndorf","year":"2000","unstructured":"Dorndorf, U., Pesch, E., & Phan-Huy, T. (2000). A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalised precedence constraints. Management Science, 46(10), 1365\u20131384.","journal-title":"Management Science"},{"key":"647_CR15","volume-title":"Computers and intractability","author":"MR Garey","year":"2002","unstructured":"Garey, M. R., & Johnson, D. S. (2002). Computers and intractability (Vol. 29). New York: W.H. freeman."},{"issue":"3","key":"647_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10951-013-0354-9","volume":"17","author":"M Haouari","year":"2014","unstructured":"Haouari, M., Kooli, A., N\u00e9ron, E., & Carlier, J. (2014). A preemptive bound for the resource constrained project scheduling problem. Journal of Scheduling, 17(3), 237\u2013248.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"647_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.disopt.2007.10.003","volume":"5","author":"JR Hardin","year":"2008","unstructured":"Hardin, J. R., Nemhauser, G. L., & Savelsbergh, M. W. (2008). Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements. Discrete Optimization, 5(1), 19\u201335.","journal-title":"Discrete Optimization"},{"issue":"1","key":"647_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2009.11.005","volume":"207","author":"S Hartmann","year":"2010","unstructured":"Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), 1\u201314.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"647_CR19","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/S0377-2217(02)00136-4","volume":"144","author":"R Heilmann","year":"2003","unstructured":"Heilmann, R. (2003). A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 144(2), 348\u2013365.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"647_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0305-0548(97)00055-5","volume":"25","author":"W Herroelen","year":"1998","unstructured":"Herroelen, W., De Reyck, B., & Demeulemeester, E. (1998). Resource-constrained project scheduling: A survey of recent developments. Computers & Operations Research, 25(4), 279\u2013302.","journal-title":"Computers & Operations Research"},{"key":"647_CR21","unstructured":"Johnson, T. J. R. (1967). An algorithm for the resource constrained project scheduling problem. Doctoral dissertation, Massachusetts Institute of Technology."},{"key":"647_CR22","first-page":"147","volume-title":"Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. Project scheduling","author":"R Kolisch","year":"1999","unstructured":"Kolisch, R., & Hartmann, S. (1999). Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. Project scheduling (pp. 147\u2013178). Berlin: Springer."},{"issue":"1","key":"647_CR23","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.ejor.2005.01.065","volume":"174","author":"R Kolisch","year":"2006","unstructured":"Kolisch, R., & Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174(1), 23\u201337.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"647_CR24","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0377-2217(96)00170-1","volume":"96","author":"R Kolisch","year":"1997","unstructured":"Kolisch, R., & Sprecher, A. (1997). PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program. European Journal of Operational Research, 96(1), 205\u2013216.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"647_CR25","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.cor.2009.12.011","volume":"38","author":"O Kon\u00e9","year":"2011","unstructured":"Kon\u00e9, O., Artigues, C., Lopez, P., & Mongeau, M. (2011). Event-based MILP models for resource-constrained project scheduling problems. Computers & Operations Research, 38(1), 3\u201313.","journal-title":"Computers & Operations Research"},{"key":"647_CR26","unstructured":"Lasserre, J. B., & Queyranne, M. (1992). Generic scheduling polyhedra and a new mixed-integer formulation for single-machine scheduling. In Proceedings of the 2nd IPCO (integer programming and combinatorial optimization) conference (pp. 136\u2013149), Pittsburgh, May 1992."},{"issue":"5","key":"647_CR27","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1287\/mnsc.44.5.714","volume":"44","author":"A Mingozzi","year":"1998","unstructured":"Mingozzi, A., Maniezzo, V., Ricciardelli, S., & Bianco, L. (1998). An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Management Science, 44(5), 714\u2013729.","journal-title":"Management Science"},{"issue":"3","key":"647_CR28","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/mnsc.49.3.330.12737","volume":"49","author":"RH M\u00f6hring","year":"2003","unstructured":"M\u00f6hring, R. H., Schulz, A. S., Stork, F., & Uetz, M. (2003). Solving project scheduling problems by minimum cut computations. Management Science, 49(3), 330\u2013350.","journal-title":"Management Science"},{"issue":"2","key":"647_CR29","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.ejor.2014.05.036","volume":"239","author":"A Naber","year":"2014","unstructured":"Naber, A., & Kolisch, R. (2014). MIP models for resource-constrained project scheduling with flexible resource profiles. European Journal of Operational Research, 239(2), 335\u2013348.","journal-title":"European Journal of Operational Research"},{"key":"647_CR30","unstructured":"Nattaf, M., Kis, T. Artigues, C., & Lopez, P. (2017). Polyhedral results and valid inequalities for the continuous energy-constrained scheduling problem. In Workshop on models and algorithms for planning and sheduling problems (MAPSP 2017), Seeon-Seebruck, Germany."},{"issue":"2","key":"647_CR31","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0377-2217(93)90062-R","volume":"67","author":"RAV Olaguibel","year":"1993","unstructured":"Olaguibel, R. A. V., & Goerlich, J. T. (1993). The project scheduling polyhedron: Dimension, facets and lifting theorems. European Journal of Operational Research, 67(2), 204\u2013220.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"647_CR32","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1287\/mnsc.16.1.93","volume":"16","author":"AAB Pritsker","year":"1969","unstructured":"Pritsker, A. A. B., Waiters, L. J., & Wolfe, P. M. (1969). Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16(1), 93\u2013108.","journal-title":"Management Science"},{"key":"647_CR33","first-page":"3","volume-title":"Polyhedral approaches to machine scheduling","author":"M Queyranne","year":"1994","unstructured":"Queyranne, M., & Schulz, A. S. (1994). Polyhedral approaches to machine scheduling (p. 3). Fachbereich: TU-Berlin."},{"key":"647_CR34","volume-title":"Combinatorial optimization: Polyhedra and efficiency","author":"A Schrijver","year":"2002","unstructured":"Schrijver, A. (2002). Combinatorial optimization: Polyhedra and efficiency (Vol. 24). Berlin: Springer."},{"key":"647_CR35","unstructured":"Schutt, A., Feydy, T., & Stuckey, P. J. (2013). Explaining time-table-edge-finding propagation for the cumulative resource constraint. In International conference on AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 234\u2013250). Berlin: Springer."},{"issue":"2","key":"647_CR36","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/S0377-2217(97)00348-2","volume":"107","author":"A Sprecher","year":"1998","unstructured":"Sprecher, A., & Drexl, A. (1998). Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. European Journal of Operational Research, 107(2), 431\u2013450.","journal-title":"European Journal of Operational Research"},{"key":"647_CR37","unstructured":"Stork, F. (2001). Stochastic resource-constrained project scheduling. Ph.D. Thesis, Technische Universit\u00e4t Berlin."},{"key":"647_CR38","unstructured":"Tesch, A. (2018). Improving energetic propagations for cumulative scheduling. In International conference on principles and practice of constraint programming (pp. 629\u2013645). Cham: Springer."},{"key":"647_CR39","doi-asserted-by":"crossref","unstructured":"Vilim, P. (2011). Timetable edge finding filtering algorithm for discrete cumulative resources. In Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (Vol. 6697, pp. 230\u2013245).","DOI":"10.1007\/978-3-642-21311-3_22"},{"key":"647_CR40","volume-title":"Project scheduling: Recent models, algorithms and applications","year":"2012","unstructured":"Weglarz, J. (Ed.). (2012). Project scheduling: Recent models, algorithms and applications (Vol. 14). Berlin: Springer."},{"issue":"8","key":"647_CR41","doi-asserted-by":"publisher","first-page":"2101","DOI":"10.1002\/aic.11522","volume":"54","author":"JC Zapata","year":"2008","unstructured":"Zapata, J. C., Hodge, B. M., & Reklaitis, G. V. (2008). The multimode resource constrained multiproject scheduling problem: Alternative formulations. AIChE Journal, 54(8), 2101\u20132119.","journal-title":"AIChE Journal"},{"issue":"3","key":"647_CR42","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1287\/ijoc.1040.0121","volume":"18","author":"G Zhu","year":"2006","unstructured":"Zhu, G., Bard, J. F., & Yu, G. (2006). A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. INFORMS Journal on Computing, 18(3), 377\u2013390.","journal-title":"INFORMS Journal on Computing"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-020-00647-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-020-00647-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-020-00647-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T00:56:05Z","timestamp":1614041765000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-020-00647-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,24]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["647"],"URL":"https:\/\/doi.org\/10.1007\/s10951-020-00647-6","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,24]]},"assertion":[{"value":"24 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}