A characterization of optimal multiprocessor schedules and new dominance rules
- PDF / 607,700 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 86 Downloads / 165 Views
A characterization of optimal multiprocessor schedules and new dominance rules Rico Walter1 · Alexander Lawrinenko1
© The Author(s) 2020
Abstract The paper on hand approaches the classical makespan minimization problem on identical parallel machines from a rather theoretical point of view. Using an approach similar to the idea behind inverse optimization, we identify a general structural pattern of optimal multiprocessor schedules. We also show how to derive new dominance rules from the characteristics of optimal solutions. Results of our computational study attest to the efficacy of the new rules. They are particularly useful in limiting the search space when each machine processes only a few jobs on average. Keywords Scheduling · Identical parallel machines · Makespan · Solution structure · Dominance rules
1 Introduction The present paper is concerned with the multiprocessor scheduling problem. Given a set M = {M1 , . . . , Mm } of m ≥ 2 identical parallel machines and a set J = {J1 , . . . , Jn } of n > m independent jobs with positive processing times p1 , p2 , . . . , pn , the objective is to assign the jobs to the machines so that the latest machine completion time (also called makespan) Cmax = max{C1 , . . . , Cm }—with Ci being the sum of processing times of all jobs assigned to Mi —is minimized. Preemption is not allowed. Using the three-field notation of Graham et al. (1979) this problem is abbreviated as P||Cmax . In the literature, P||Cmax is also known as the makespan minimization problem on identical parallel machines.
B
Rico Walter [email protected] https://www.mansci.uni-jena.de Alexander Lawrinenko [email protected]
1
Chair for Management Science, Friedrich Schiller University Jena, Carl-Zeiß-Straße 3, 07743 Jena, Germany
123
Journal of Combinatorial Optimization
The N P-hard problem P||Cmax (see Garey and Johnson 1979) represents one of the very basic and fundamental problems in scheduling theory. It has received and still receives a lot of attention from both the academic world and practitioners. The large body of literature, that has evolved over the years, contains papers on approximation algorithms, (meta-)heuristics, exact solution procedures, and lower bounding techniques. From the numerous publications on (meta-)heuristic algorithms within the last two decades, we selected the following few ones to outline the broad range of near-optimal solution approaches. Alvim and Ribeiro (2004) exploited the “dual” relation between P||Cmax and the bin packing problem (BPP). They proposed a hybrid improvement heuristic that consists of construction, redistribution, and improvement phases. In the latter phase, tabu search is applied. Frangioni et al. (2004) proposed new neighborhood operators for local search algorithms that perform multiple exchanges of jobs among machines. Dell’Amico et al. (2008) presented an effective meta-heuristic algorithm based on the scatter search paradigm. Kashan and Karimi (2009) presented a discrete particle swarm optimization algorithm and a hybrid v
Data Loading...
