Skip to Main content Skip to Navigation
Journal articles

Scheduling two interfering job sets on uniform parallel machines with makespan and cost functions

Donatas Elvikis 1 Horst Hamacher 1 Vincent t'Kindt 2 
2 ROOT - Recherche Opérationnelle, Ordonnancement, Transport ERL 7002
LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours, CNRS - Centre National de la Recherche Scientifique : EMR7002 / ERL7002
Abstract : We consider the problem of scheduling two jobs A and B on a set of m uniform parallel machines. Each job is assumed to be independent from the other: job A and job B are made up of n_A and n_B operations, respectively. Each operation is defined by its processing time and possibly additional data such as a due date, a weight, etc., and must be processed on a single machine. All machines are uniform, i.e. each machine has its own processing speed. Notice that we consider the special case of equal-size operations, i.e. all operations have the same processing time. The scheduling of operations of job A must be achieved to minimize a general cost function F_A , whereas it is the makespan that must be minimized when scheduling the operations of job B. These kind of problems are called multiple agent scheduling prob- lems. As we are dealing with two conflicting criteria, we focus on the calculation of strict Pareto optima for F_A and C^B_max criteria. In this paper we consider different min-max and min-sum versions of function F_A and provide special properties as well as polynomial time algorithms.
Document type :
Journal articles
Complete list of metadata
Contributor : Vincent T'Kindt Connect in order to contact the contributor
Submitted on : Tuesday, June 10, 2014 - 4:50:44 PM
Last modification on : Tuesday, May 10, 2022 - 1:44:01 PM

Links full text



Donatas Elvikis, Horst Hamacher, Vincent t'Kindt. Scheduling two interfering job sets on uniform parallel machines with makespan and cost functions. Journal of Scheduling, Springer Verlag, 2011, 14 (5), pp.471-481. ⟨10.1007/s10951-010-0201-1⟩. ⟨hal-01003801⟩



Record views