{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T16:46:05Z","timestamp":1700671565828},"reference-count":11,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T00:00:00Z","timestamp":1271808000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2010,12]]},"abstract":"Abstract<\/jats:title>It is known that the resource\u2010unconstrained project scheduling problem with generalized precedence constraints (RUPSP) and minimum completion time objective function can be solved in time O<\/jats:italic>(n<\/jats:italic>\u00b7m<\/jats:italic>), where n<\/jats:italic> is the number of activities and m<\/jats:italic> is the number of precedence relations. In this article, we propose a new network formulation for RUPSP based on a transformation that maps the original problem into a standardized acyclic network where precedence relationships between each pair of activities are only of the finish\u2010to\u2010start type with zero time lags. With this network, we then associate a mathematical program that can be solved in O<\/jats:italic>(m<\/jats:italic>) time by means of dynamic programing. Exploiting the dual formulation of this mathematical program we further prove that the minimum completion time can also be computed, with the same computational complexity O<\/jats:italic>(m<\/jats:italic>), by finding an augmenting path of longest length in the proposed acyclic network by installing unit capacities on arcs. Computational results on benchmarks are presented. \u00a9 2010 Wiley Periodicals, Inc. NETWORKS, 2010<\/jats:p>","DOI":"10.1002\/net.20388","type":"journal-article","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T21:08:54Z","timestamp":1271884134000},"page":"263-271","source":"Crossref","is-referenced-by-count":11,"title":["A new formulation of the resource\u2010unconstrained project scheduling problem with generalized precedence relations to minimize the completion time"],"prefix":"10.1002","volume":"56","author":[{"given":"Lucio","family":"Bianco","sequence":"first","affiliation":[]},{"given":"Massimiliano","family":"Caramia","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2010,11,23]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Network flows","author":"Ahuja R. K.","year":"1993"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02283745"},{"key":"e_1_2_1_4_2","unstructured":"B.De Reyck Scheduling projects with generalized precedence relations: Exact and heuristic approaches Ph.D. Thesis Department of Applied Economics Katholieke Universiteit Leuven Leuven Belgium 1998."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-57506-8"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.38.9.1245"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251876"},{"key":"e_1_2_1_8_2","first-page":"347","volume-title":"Industrial scheduling","author":"Kelley J. E.","year":"1963"},{"key":"e_1_2_1_9_2","volume-title":"Project management with CPM, PERT and precedence diagramming","author":"Moder J. J.","year":"1983"},{"key":"e_1_2_1_10_2","series-title":"Project scheduling with time windows and scarce resources, Lecture Notes in Economics and Mathematical Systems","author":"Neumann K.","year":"2002"},{"key":"e_1_2_1_11_2","volume-title":"Combinatorial optimization, algorithms and complexity","author":"Papadimitriou C. H.","year":"1982"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02022042"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20388","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20388","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T16:18:36Z","timestamp":1700669916000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20388"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,23]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1002\/net.20388"],"URL":"https:\/\/doi.org\/10.1002\/net.20388","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,23]]}}}