Neighbourhood properties in some single processor scheduling problem with variable efficiency and additional resources

• Autorzy: Gorczyca M. , Janiak A. , Janiak W.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

scheduling; optimization; resource allocation; neighbourhood

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2011
• Tom: Vol. 5, no. 1-2
• Strony: 5--17
• Opis fizyczny: Bibliogr. [20] poz., rys.

Twórcy

autor

Gorczyca M.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Z. Janiszewskiego 11/17, 50-372 Wrocław, Poland.

autor

Janiak A.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Z. Janiszewskiego 11/17, 50-372 Wrocław, Poland.

autor

Janiak W.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Z. Janiszewskiego 11/17, 50-372 Wrocław, Poland.

Bibliografia

• Burkov, V., 1966. Resource allocation as a time-optimal control problem. (in Russian). Avtomat. i Telemeh., 27(2), 114–129.
• Denning, P. J., 1980. Working sets past and present. IEEE Transactions on Software Engineering, 6(1), 64–84.
• Janiak, A., 1989. Minimization of the blooming mill standstills mathematical model – suboptimal algorithms. Zeszyty Naukowe Akademii Górniczo-Hutniczej s. Mechanika, 8(2), 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), 264–271.
• Janiak, A., Przysada, J., 1996a. Czasowo-optymalne szeregowanie zadań z rożnymi terminami gotowości na równoległych maszynach. Zeszyty Naukowe Politechniki Śląskiej s. Automatyka, 117, 99–109.
• Janiak, A., Przysada, J., 1996b. Zastosowanie systemów wieloprocesorowych w zrobotyzowanych systemach sterowania. In Materiały V Krajowej Konferencji Robotyki, vol. 2, 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, 101–107.
• Józefowska, J., Mika, M., Różycki, R., Waligóra, G., and Węglarz, J., 1997a. Discretecontinuous scheduling to minimize maximum lateness. In Proceedings of the Fourth International Symposium on Methods and Models in Automation and Robotics MMAR’97, 947–952.
• Józefowska, J., Mika, M., Różycki, R., Waligóra, G., and Węglarz, J., 1997b. Discretecontinuous scheduling to minimize the mean flow time – computational experiments. Computational Methods in Science and Technology, 3, 25–37.
• Józefowska, J., Mika, M., Różycki, R., Waligóra, G., and Węglarz, J., 1998. Local search metaheuristics for discrete-continuous scheduling problems. European Journal of Operational Research, 107(2), 354–370.
• Jozefowska, J., Waligóra, G., and Węglarz, J., 2002. Tabu list management methods for a discrete-continuous scheduling problem. European Journal of Operational Research, 137(2), 288–302.
• Józefowska, J., Węglarz, J., 1996. Discrete-continuous scheduling problems - mean completion time results. European Journal of Operational Research, 94(2), 302–309.
• Józefowska, J., Węglarz, J., 1998. On a methodology for discrete-continuous scheduling. European Journal of Operational Research, 107(2), 338–353.
• Nowicki, E., Zdrzałka, S., 1984. Optimal control policies for resource allocation in an activity network. European Journal of Operational Research, 16(2), 198–214.
• Schittowski, K., 1985. Nlqpl: A fortran-subroutine solving constrained nonlinear programming problems. Annals of Operations Research, 5, 485–500.
• Waligóra, G., 2009. Tabu search for discrete-continuous scheduling problems with heuristic continuous resource allocation. European Journal of Operational Research, 193(3), 849–856.
• Węglarz, J., 1979. Project scheduling with discrete and continuous resources. IEEE Transactions on Systems, Man and Cybernetics, 9(10), 644–650.
• Węglarz, J., 1980. Multiprocessor scheduling with memory allocation – a deterministic approach. IEEE Transactions on Computers, 29(8), 703–709.
• Węglarz, J., 1989. Scheduling under continuous performing speed vs. resource amount activity models. In Advances in Project Scheduling, Słowiński, R. and Węglarz, J., editors. Elsevier Science Publishers, Amsterdam, 273–295.
• Węglarz, J., 1991. Synthesis problems in allocating continuous, doubly constrained resources among activities. In Proceedings of the XI Triennal International Conference on Operational Research IFORS’90, Pergamon Press, Oxford, 715–724