×

zbMATH — the first resource for mathematics

Modeling block structured project scheduling with resource constraints. (English) Zbl 1437.68162
Lirkov, Ivan (ed.) et al., Large-scale scientific computing. 12th international conference, LSSC 2019, Sozopol, Bulgaria, June 10–14, 2019. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 11958, 484-492 (2020).
Summary: We propose a formal model of block-structured project scheduling with resource constraints, with the goal of designing optimization algorithms. We combine block structured modeling of business processes with results from project scheduling literature. Differently from standard approaches, here we focus on block structured scheduling processes. Our main achievement is the formulation of an abstract mathematical model of block-structured resource-constrained scheduling processes. We tested the correctness and feasibility of our approach using an initial experimental prototype based on Constraint Logic Programming.
For the entire collection see [Zbl 1435.65015].
MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68N17 Logic programming
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
90B35 Deterministic scheduling theory in operations research
Software:
PSPLIB; Gecode
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bădică, A., Bădică, C., Dănciulescu, D., Logofătu, D.: Greedy heuristics for automatic synthesis of efficient block-structured scheduling processes from declarative specifications. In: Iliadis, L., Maglogiannis, I., Plagianakos, V. (eds.) AIAI 2018. IAICT, vol. 519, pp. 183-195. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92007-8_16
[2] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Franisco (1979) · Zbl 0411.68039
[3] Kelley Jr., J.E.: Critical-path planning and scheduling: mathematical basis. Oper. Res. 9(3), 296-320 (1961). https://doi.org/10.1287/opre.9.3.296. Informs · Zbl 0098.12103
[4] Kolisch, R., Sprecher, A.: PSPLIB - a project scheduling library. Eur. J. Oper. Res. 96(1), 205-216 (1997). https://doi.org/10.1016/S0377-2217(96)00170-1. Elsevier · Zbl 0947.90587
[5] Pesic, M., van der Aalst, W.M.P.: A declarative approach for flexible business processes management. In: Eder, J., Dustdar, S. (eds.) BPM 2006. LNCS, vol. 4103, pp. 169-180. Springer, Heidelberg (2006). https://doi.org/10.1007/11837862_18
[6] Mrasek, R., Mülle, J., Böhm, K.: Process synthesis with sequential and parallel constraints. In: Debruyne, C., et al. (eds.) On the Move to Meaningful Internet Systems, vol. 10033, pp. 43-60. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48472-3_3
[7] Niederliński, A.: A Gentle Guide to Constraint Logic Programming via ECLiPSe, 3rd edn. Jacek Skalmierski Computer Studio, Gliwice (2014)
[8] Schimpf, J., Shen, K.: ECLiPSe - from LP to CLP. Theor. Pract. Log. Program. 12(1-2), 127-156 (2012). https://doi.org/10.1017/S1471068411000469. Cambridge University Press · Zbl 1244.68020
[9] Sindelar, M., Sitaraman, R.K., Shenoy, P.: Sharing-aware algorithms for virtual machine colocation. In: Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 367-378. ACM (2011). https://doi.org/10.1145/1989493.1989554
[10] Ullman, J.D.: NP-complete scheduling problems. J. Comput. Syst. Sci. 10(3), 384-393 (1975). https://doi.org/10.1016/S0022-0000(75)80008-0. Academic Press · Zbl 0313.68054
[11] The ECLiPSe Constraint Programming System. http://www.eclipseclp.org/. Accessed Mar 2019
[12] Gecode - Generic Constraint Development Environment. https://www.gecode.org/. Accessed Mar 2019
[13] Project Scheduling Problem Library - PSPLIB. · Zbl 0947.90587
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.