Open AccessNeighbourhood Properties in Some Single Processor Scheduling Problem with Variable Efficiency and Additional Resources
Author(s) -
Mateusz Gorczyca,
Adam Janiak,
Władysław Janiak
Publication year - 2011
Publication title -
decision making in manufacturing and services
Language(s) - English
Resource type - Journals
eISSN - 2300-7087
pISSN - 1896-8325
DOI - 10.7494/dmms.2011.5.1.5
Subject(s) - mathematical optimization , computer science , scheduling (production processes) , preprocessor , bounded function , heuristics , metaheuristic , simulated annealing , algorithm , mathematics , artificial intelligence , mathematical analysis
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.