Multi-machine Scheduling with Setup Times
In this paper we are considering the problem of tasks scheduling executed simultaneously on multiple identical machines with a cost-criterion, which is the product of the tasks execution time and the number of used machines. Moreover, it is assumed that b
- PDF / 410,384 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 231 Views
Department of Automatics, Mechatronics and Control Systems, Faculty of Electronics, Wroclaw University of Science and Technology, Wyb. Wyspia´ nskiego 27, 50-370 Wroclaw, Poland {wojciech.bozejko,lukasz.kacprzak}@pwr.edu.pl 2 Faculty of Technical and Economic Science, The Witelon State University of Applied Sciences in Legnica, Sejmowa 5a, 59-220 Legnica, Poland [email protected] 3 Institute of Computer Science, University of Wroclaw, Joliot-Curie 15, 50-383 Wroclaw, Poland [email protected] Abstract. In this paper we are considering the problem of tasks scheduling executed simultaneously on multiple identical machines with a costcriterion, which is the product of the tasks execution time and the number of used machines. Moreover, it is assumed that between the tasks performed sequentially there must be setup of the machines performed. Solution to the problem comes down to a generalization of a two-dimensional packing problem. The paper presents simulated annealing algorithm with different variants of packing strategy. The conducted computational experiments proved that designated solution differs little from some lower bounds for the constraints of the objective function.
1
Introduction
In the vast majority of the considered in the literature scheduling problems, it is assumed that a task is done on a single machine. However, in many real production processes, in particular - modern computational systems - a task execution requires the use of more than one machine (CPU), Bo˙zejko et al. [5]. Then, we can talk about systems with parallel machines and multi-machine (multiprocessor) tasks. We can meet such an approach also in cloud exploration [17]. In literature, such problems have been considered for a long time, for instance in the work of Drozdowski [8,10] and in the monograph [9], Fleitelson [11], as well as in doctoral thesis of Kramer [13] where they mainly concern computer systems. The first applications of multi-machine models of tasks scheduling refer not only to chemical industry (Bozoki and Richard [3]) but also to projects scheduling (Vizing [18]). The natural reference for this type of tasks are, examined from decades, multiprocessor computer systems (Bla˙zewicz et al. [1]). In the vast majority of them the completion date of the execution of all tasks (Cmax ) was maximized. Today, many computer centers offer performance of calculations c IFIP International Federation for Information Processing 2016 Published by Springer International Publishing Switzerland 2016. All Rights Reserved K. Saeed and W. Homenda (Eds.): CISIM 2016, LNCS 9842, pp. 300–311, 2016. DOI: 10.1007/978-3-319-45378-1 27
Multi-machine Scheduling with Setup Times
301
and the cost of the service depends not only on the duration of the computations but also on the number of required processors. Therefore, there appears a need for the construction and testing of new, corresponding to the reality models and analysis of criterion functions taking into account the overall costs. We can encouter similar issues
Data Loading...
