Neighbourhood Properties in Some Single Processor Scheduling Problem with Variable Efficiency and Additional Resources
DOI:
https://doi.org/10.7494/dmms.2011.5.1.5Keywords:
scheduling, optimization, resource allocation, neighbourhoodAbstract
In the paper, we consider a problem of scheduling a set of tasks on a single processor. Each task must be preprocessed before it can be started on a processor. The efficiency of preprocessing is variable, i.e., the rate of the task preprocessing depends on the amount of continuously divisible resource allotted to this task. This dependency is given by concave, continuous, non-negative and strictly increasing function of the resource amount. The total consumption of resource at each moment is upper bounded. The objective is to minimize the maximum task completion time. The considered problem is NP-hard. Such a problem appears, e.g., in steel mill systems, where ingots (before hot rolling on the blooming mill) have to achieve the required temperature in the preheating process in soaking pits. Some new properties of the problem are proved. These properties are used to construct the procedure for evaluation of the neighbourhood. The procedure is proposed to improve the efficiency of algorithms based on the neighbourhood concept, such as metaheuristics. The computational experiment is conducted to examine the efficiency of the proposed procedure. The described approach can be easily used in the other discrete-continuous scheduling problems.
References
Burkov V.N. (1966). Resource allocation as a time-optimal control problem [in Russian]. Avtomatika i Telemekhanika, 27(2), pp. 114–129.
Denning P.J. (1980). Working sets past and present. IEEE Transactions on Software Engineering, SE-6(1), pp. 64–84. DOI: http://doi.org/10.1109/TSE.1980.230464.
Janiak A. (1989). Minimization of the blooming mill standstills—mathematical model, suboptimal algorithms. Zeszyty Naukowe Akademii Górniczo-Hutniczej. Mechanika, 8(2), pp. 37–49.
Janiak A. & Janiak W. (2011). Single-processor scheduling problem with dynamic models of task release dates. IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, 41(2), pp. 264–271. DOI: http://doi.org/10.1109/TSMCA.2010.2058099.
Janiak A. & Przysada J. (1996a). Czasowo-optymalne szeregowanie zadań z różnymi terminami gotowości na równoległych maszynach. Zeszyty Naukowe Politechniki Śląskiej. Seria: Automatyka, 117, pp. 99–109.
Janiak A. & Przysada J. (1996b). Zastosowanie systemów wieloprocesorowych w zrobotyzowanych systemach sterowania. In: Materiały V Krajowej Konferencji Robotyki, vol. 2, pp. 149–158.
Janiak A. & Przysada J. (1997). Algorytmy szeregowania zadań i rozdziału zasobów na procesorach równoległych – przykłady zastosowań. In: Materiały III Konferencji Komputerowe Systemy Wielodostępne, pp. 101–107.
Józefowska J., Mika M., Różycki R., Waligóra G. & Węglarz J. (1997a). Discrete-continuous scheduling to minimize maximum lateness. In: Proceedings of the Fourth International Symposium on Methods and Models in Automation and Robotics (MMAR’97), pp. 947–952.
Józefowska J., Mika M., Różycki R., Waligóra G. & Węglarz J. (1997b). Discrete-continuous scheduling to minimize the mean flow time—computational experiments. Computational Methods in Science and Technology, 3(1), pp. 25–37. DOI: http://doi.org/10.12921/cmst.1997.03.01.25-37.
Józefowska J., Mika M., Różycki R., Waligóra G. & Węglarz J. (1998). Local search metaheuristics for discrete-continuous scheduling problems. European Journal of Operational Research, 107(2), pp. 354–370. DOI: http://doi.org/10.1016/S0377-2217(97)00345-7.
Józefowska J., Waligóra G. & Węglarz J. (2002). Tabu list management methods for a discrete-continuous scheduling problem. European Journal of Operational Research, 137(2), pp. 288–302. DOI: http://doi.org/10.1016/S0377-2217(01)00210-7.
Józefowska J. & Węglarz J. (1996). Discrete-continuous scheduling problems—mean completion time results. European Journal of Operational Research, 94(2), pp. 302–309. DOI: http://doi.org/10.1016/0377-2217(96)00130-0.
Józefowska J. & Węglarz J. (1998). On a methodology for discrete-continuous scheduling. European Journal of Operational Research, 107(2), pp. 338–353. DOI: http://doi.org/10.1016/S0377-2217(97)00346-9.
Nowicki E. & Zdrzałka S. (1984). Optimal control policies for resource allocation in an activity network. European Journal of Operational Research, 16(2), pp. 198–214. DOI: http://doi.org/10.1016/0377-2217(84)90074-2.
Schittkowski K. (1986). NLPQL: A FORTRAN subroutine solving constrained nonlinear programming problems. Annals of Operations Research, 5, pp. 485–500. DOI: http://doi.org/10.1007/BF02739235.
Waligóra G. (2009). Tabu search for discrete-continuous scheduling problems with heuristic continuous resource allocation. European Journal of Operational Research, 193(3), pp. 849–856. DOI: http://doi.org/10.1016/j.ejor.2007.11.009.
Węglarz J. (1979). Project scheduling with discrete and continuous resources. IEEE Transactions on Systems, Man, and Cybernetics, SMC-9(10), pp. 644–650. DOI: http://doi.org/10.1109/TSMC.1979.4310093.
Węglarz J. (1980). Multiprocessor scheduling with memory allocation—a deterministic approach. IEEE Transactions on Computers, C-29(8), pp. 703–709. DOI: http://doi.org/10.1109/TC.1980.1675652.
Węglarz J. (1989). Scheduling under continuous performing speed vs. resource amount activity models. In: Słowiński R. & Węglarz J. (Eds.), Advances in Project Scheduling. Elsevier Science Publishers, Amsterdam, pp. 273–295.
Węglarz J. (1991). Synthesis problems in allocating continuous, doubly constrained resources among dynamic activities. In: Bradley H.E. (Ed.), Operational Research ’90: Selected Papers from the 12th IFORS International Conference. Pergamon Press, Oxford, pp. 715–725.
