Discrete-continuous project scheduling with preemptable activities

• Autorzy: Różycki R. , Waligóra G. , Węglarz J.

Identyfikatory

DOI

10.1515/bpasts-2016-0043

• Języki publikacji: EN

Abstrakty

EN

In this paper, discrete-continuous project scheduling problems with preemptable activities are considered. In these problems, activities of a project simultaneously require discrete and continuous resources for their execution. The activities are preemptable, and the processing rate of each activity is a continuous, increasing function of the amount of a single continuous resource allotted to the activity at a time. The problem is to find a precedence- and discrete resource-feasible schedule and, simultaneously, continuous resource allocation that would minimize the project duration. Convex and concave processing rate functions are considered separately. We show that for convex functions the problem is simple, whereas for concave functions a special methodology has to be developed. We discuss the methodology for three cases of the problem: no discrete resource constraints, one discrete resource being a set of parallel, identical machines, and an arbitrary number of discrete resources. In each case we analyze separately independent and precedence-related activities. Some conclusions and directions for future research are given.

Słowa kluczowe

EN

project scheduling; discrete-continuous; preemptable activities; project duration

PL

planowanie projektu; dane dyskretne ciągłe; czas trwania projektu

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2016
• Tom: Vol. 64, nr 2
• Strony: 383--393
• Opis fizyczny: Bibliogr. 22 poz., tab., rys., wykr.

Twórcy

autor

Różycki R.

• Institute of Computing Science, Poznan University of Technology, 2 Piotrowo St., 60-965 Poznan, Poland

autor

Waligóra G.

• Institute of Computing Science, Poznan University of Technology, 2 Piotrowo St., 60-965 Poznan, Poland

autor

Węglarz J.

• Institute of Computing Science, Poznan University of Technology, 2 Piotrowo St., 60-965 Poznan, Poland

Bibliografia

• [1] J. Józefowska, M. Mika, R. Różycki, G. Waligóra, and J. Węglarz, “Local search metaheuristics for discrete-continuous scheduling problems”, European Journal of Operational Research 107 (2), 354-370 (1998).
• [2] J. Józefowska, M. Mika, R. Różycki, G. Waligóra, and J. Węglarz, “Discrete-continuous scheduling to minimize the makespan with power processing rates of jobs”, Discrete Applied Mathematics 94 (1-3), 263-285 (1999).
• [3] J. Józefowska, M. Mika, R. Różycki, G. Waligóra, and J. Węglarz, “A heuristic approach to allocating the continuous resource in discrete-continuous scheduling problems to minimize the makespan”, Journal of Scheduling 5 (6), 487-499 (2002).
• [4] J. Józefowska, G. Waligóra, and J. Węglarz, “Tabu list management methods for a discrete-continuous scheduling problem”, European Journal of Operational Research 137 (2), 288-302 (2002). 1] J. Józefowska, M. Mika, R. Różycki, G. Waligóra, and J. Węglarz, “Local search metaheuristics for discrete-continuous scheduling problems”, European Journal of Operational Research 107 (2), 354-370 (1998).
• [5] G. Waligóra, “Tabu search for discrete-continuous scheduling problems with heuristic continuous resource allocation”, European Journal of Operational Research 193 (3), 849-856 (2009).
• [6] M.S. Barketau, M.Y. Kovalyov, J. Węglarz, and M. Machowiak, “Scheduling arbitrary number of malleable tasks on multiprocessor systems”, Bull. Pol. Ac.: Tech. 62 (2), 255-261 (2014).
• [7] R. Różycki and J. Węglarz, “On job models in power management problems”, Bull. Pol. Ac.: Tech. 57 (2), 147-151 (2009)
• [8] R. Różycki and J. Węglarz, “Power-aware scheduling of preemptable jobs on identical parallel processors to meet deadlines”, European Journal of Operational Research 218 (1), 68-75 (2012).
• [9] R. Różycki and J. Węglarz, „Power-aware scheduling of preemptable jobs on identical parallel processors to minimize makespan”, Annals of Operations Research 213 (1), 235-252 (2014).
• [10] R. Różycki and J. Węglarz, “Solving a power-aware scheduling problem by grouping jobs with the same processing characteristic”, Discrete Applied Mathematics 182, 150-161 (2015).
• [11] J. Józefowska, M. Mika, R. Różycki, G. Waligóra, and J. Węglarz, “Solving the discrete-continuous project scheduling problem via its discretization”, Mathematical Methods of Operations Research 52 (3), 489-499 (2000).
• [12] M. Mika, G. Waligóra, and J. Węglarz, “Modelling and solving grid resource allocation problem with network resources for workflow applications”, Journal of Scheduling 14 (3), 291-306 (2011).
• [13] G. Waligóra, “Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan”, Computational Optimization and Applications 48 (2), 399-421 (2011).
• [14] G. Waligóra, “Discrete-continuous project scheduling with discounted cash flows - a tabu search approach”, Computers & Operations Research 35 (7), 2141-2153 (2008).
• [15] G. Waligóra, “Discrete-continuous project scheduling with discounted cash inflows and various payment models - a review of recent results”, Annals of Operations Research 213 (1), 319-340 (2014).
• [16] G. Waligóra, “Simulated annealing and tabu search for discrete- continuous project scheduling with discounted cash flows”, RAIRO - Operations Research 48 (1), 1-24 (2014).
• [17] J. Węglarz, “Time-optimal control of resource allocation in a complex of operations framework”, IEEE Transactions on Systems, Man and Cybernetics 6 (11), 783-788 (1976).
• [18] J. Węglarz, “Multiprocessor scheduling with memory allocation - a deterministic approach”, IEEE Transactions on Computers 29 (8), 703-709 (1980).
• [19] E.L. Demeulemeester and W.S. Herroelen, Project Scheduling - A Research Handbook, Kluwer, Boston, 2002.
• [20] J. Węglarz, “Project scheduling with discrete and continuous resources”, IEEE Transactions on Systems, Man and Cybernetics 9 (10), 644-651 (1979).
• [21] J. Józefowska, M. Mika, R. Różycki, G. Waligóra, and J.Węglarz, “An almost optimal heuristic for preemptive Cmax scheduling of dependent tasks on identical parallel processors”, Annals of Operations Research 129 (1-4), 205-216 (2004).
• [22] J. Węglarz, J. Błażewicz, W. Cellary, and R. Słowiński, “An automatic revised simplex method for constrained resource network scheduling”, ACM Transactions on Mathematical Software 3 (3), 295-300 (1977).

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.