Zurück zu den Preprints des Jahres 2016


Heuristic algorithms to maximize the weighted revenue and weighted number of jobs processed on parallel uniform machines

by Gholami, O.; Sotskov, Y. N.; Bakhoda, S.; Werner, F..

Series: 2016-04, Preprints

90B35 Scheduling theory, deterministic

A set J = { J_1, J_2, ..., J_n } of jobs has to be processed on a set of parallel uniform machines. For each job J_i, a release time r_i >= 0 and a due date d_i > r_i are given. Each job may be processed without interruptions on any of the given machines having different speeds. If job J_i will be started and then completed within the time segment [r_i, d_i], the benefit b_i > 0 will be earned. Otherwise, this job will be rejected and the benefit b_i will be discarded. Let J(S) denote the subset of all jobs J_i processed within their intervals [r_i, d_i] in the schedule S. The set J J(S) includes all the jobs rejected from the schedule S. The criterion under consideration is to maximize the weighted sum of the benefits w_1 sum_{i in J}(S)} b_i and the weighted number of jobs w_2 |J(S)| processed according to the schedule S,
where both weights w_1 and w_2 are non-negative with the assumption that w_1 + w_2 = 1. We investigate some properties of the objective function, develop a simulated annealing algorithm, a tabu search algorithm, and a genetic algorithm for solving the above scheduling problem heuristically. The developed algorithms are tested on moderate instances with n=50 and five uniform machines and on large instances with up to 500 jobs and 50 uniform machines. It is demonstrated how to use the obtained results in scheduling practice.

Scheduling, Uniform machines, Revenue maximization, Genetic algorithm, Simulated annealing, Tabu search