Two-agent scheduling on uniform parallel machines with min-max criteria |
| |
Authors: | Donatas Elvikis Vincent T’kindt |
| |
Institution: | 1. AG Optimization, Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67663, Kaiserslautern, Germany 2. Laboratoire d’Informatique, Equipe Ordonnancement et Conduite (ERL CNRS 6305), Université Fran?ois Rabelais Tours, 64 avenue Jean Portalis, 37200, Tours, France
|
| |
Abstract: | We consider the problem of scheduling two agents A and B on a set of m uniform parallel machines. Each agent is assumed to be independent from the other: agent A and agent B are made up of n A and n B jobs, respectively. Each job 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 jobs, i.e. all jobs share the same processing time. Our goal is to minimize two maximum functions associated with agents A and B and referred to as $F_{max}^{A}=\max_{i\in A} f^{A}_{i}(C_{i})$ and $F_{max}^{B}=\max_{i\in B}f^{B}_{i}(C_{i})$ , respectively, with C i the completion time of job i and $f_{i}^{X}$ a non-decreasing function. These kinds of problems are called multi-agent scheduling problems. As we are dealing with two conflicting criteria, we focus on the calculation of the strict Pareto optima for the $(F_{max}^{A}, F_{max}^{B} )$ criteria vector. In this paper we develop a minimal complete Pareto set enumeration algorithm with time complexity and memory requirements. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|