Zurück zu den Preprints des Jahres 2016


2016-04

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

MSC:
90B35 Scheduling theory, deterministic

Abstract:
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.

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