{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:58:46Z","timestamp":1760241526626,"version":"build-2065373602"},"reference-count":17,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,4,17]],"date-time":"2018-04-17T00:00:00Z","timestamp":1523923200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider one approach to formalize the Resource-Constrained Project Scheduling Problem (RCPSP) in terms of combinatorial optimization theory. The transformation of the original problem into combinatorial setting is based on interpreting each operation as an atomic entity that has a defined duration and has to be resided on the continuous time axis meeting additional restrictions. The simplest case of continuous-time scheduling assumes one-to-one correspondence of resources and operations and corresponds to the linear programming problem setting. However, real scheduling problems include many-to-one relations which leads to the additional combinatorial component in the formulation due to operations competition. We research how to apply several typical algorithms to solve the resulted combinatorial optimization problem: enumeration including branch-and-bound method, gradient algorithm, random search technique.<\/jats:p>","DOI":"10.3390\/a11040050","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T03:51:13Z","timestamp":1524023473000},"page":"50","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Evaluating Typical Algorithms of Combinatorial Optimization to Solve Continuous-Time Based Scheduling Problem"],"prefix":"10.3390","volume":"11","author":[{"given":"Alexander A.","family":"Lazarev","sequence":"first","affiliation":[{"name":"Institute of Control Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Nekrasov","sequence":"additional","affiliation":[{"name":"Institute of Control Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolay","family":"Pravdivets","sequence":"additional","affiliation":[{"name":"Institute of Control Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,4,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Artigues, C., Demassey, S., N\u00e9ron, E., and Sourd, F. (2008). Resource-Constrained Project Scheduling Models, Algorithms, Extensions and Applications, Wiley-Interscience.","DOI":"10.1002\/9780470611227"},{"key":"ref_2","unstructured":"Meyer, H., Fuchs, F., and Thiel, K. (2009). Manufacturing Execution Systems. Optimal Design, Planning, and Deployment, McGraw-Hill."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Jozefowska, J., and Weglarz, J. (2006). Perspectives in Modern Project Scheduling, Springer.","DOI":"10.1007\/978-0-387-33768-5"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1287\/opre.8.2.219","article-title":"On the Job-Shop Scheduling Problem","volume":"8","author":"Manne","year":"1960","journal-title":"Oper. Res."},{"key":"ref_5","unstructured":"Jones, A., and Rabelo, L.C. (2017, April 10). Survey of Job Shop Scheduling Techniques, Wiley Encyclopedia of Electrical and Electronics Engineering, Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.37.1262&rep=rep1&type=pdf."},{"key":"ref_6","unstructured":"Taravatsadat, N., and Napsiah, I. (2011, January 22\u201324). Application of Artificial Intelligent in Production Scheduling: A critical evaluation and comparison of key approaches. Proceedings of the 2011 International Conference on Industrial Engineering and Operations Management, Kuala Lumpur, Malaysia."},{"key":"ref_7","unstructured":"Hao, P.C., Lin, K.T., Hsieh, T.J., Hong, H.C., and Lin, B.M.T. (2018, January 19\u201323). Approaches to simplification of job shop models. Proceedings of the 20th Working Seminar of Production Economics, Innsbruck, Austria."},{"key":"ref_8","unstructured":"Trevisan, L. (2011). Combinatorial Optimization: Exact and Approximate Algorithms, Stanford University."},{"key":"ref_9","unstructured":"Wilf, H.S. (1994). Algorithms and Complexity, University of Pennsylvania."},{"key":"ref_10","unstructured":"Jacobson, J. (1999). Branch and Bound Algorithms\u2014Principles and Examples, University of Copenhagen."},{"key":"ref_11","unstructured":"Erickson, J. (2014). Models of Computation, University of Illinois."},{"key":"ref_12","unstructured":"Ruder, S. (2016). An Overview of Gradient Descent Optimization Algorithms, NUI Galway."},{"key":"ref_13","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, Massachusetts Institute of Technology. [3rd ed.]."},{"key":"ref_14","unstructured":"Kalitkyn, N.N. (1978). Numerical Methods, Nauka. (In Russian)."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Haupt, R.L., and Haupt, S.E. (2004). Practical Genetic Algorithms, Wiley-Interscience. [2nd ed.].","DOI":"10.1002\/0471671746"},{"key":"ref_16","unstructured":"Mitchell, I. (2008). Dynamic Programming Algorithms for Planning and Robotics in Continuous Domains and the Hamilton-Jacobi Equation, University of British Columbia."},{"key":"ref_17","unstructured":"Miner, D., and Shook, A. (2013). MapReduce Design Patterns: Building Effective Algorithms and Analytics for Hadoop and Other Systems, O\u2019Reilly Media."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/50\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:01:02Z","timestamp":1760194862000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,17]]},"references-count":17,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,4]]}},"alternative-id":["a11040050"],"URL":"https:\/\/doi.org\/10.3390\/a11040050","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,4,17]]}}}