Journées de l'optimisation 2014
Incluant une Journée industrielle de l'optimisation
HEC Montréal, 5  7 mai 2014
JOPT2014
HEC Montréal, 5 — 7 mai 2014
WB7 Ordonnancement / Scheduling
7 mai 2014 11h00 – 12h40
Salle: TD Assurance Meloche Monnex
Présidée par Jacques Carlier
3 présentations

11h00  11h25
On/Off Event Based Model for the MutliObjective RCPSP with Budget Optimization
We consider Eventbased MILP formulations of RCPSP in multiobjective programming frameworks. In particular, we extend this type of models to take into account financial criteria.
References: O. Koné, C. Artigues, P. Lopez, M. Mongeau, Eventbased MILP models for resourceconstrained project scheduling problems, Computers & Operations Research, 38(1), p.313, 2011. 
11h25  11h50
A Tabu Search/Path Relinking Algorithm to Solve the Job Shop Scheduling Problem
We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to tackle the job shop scheduling problem (JSP). To test the performance of TS/PR, we apply it to tackle almost all of the benchmark JSP instances available in the literature. The test results show that TS/PR obtains competitive results compared with stateoftheart algorithms in the literature. In particular, TS/PR is able to improve the upper bounds for 49 out of the 205 tested instances and it solves a challenging instance that has remained unsolved for over 20 years.

11h50  12h15
New Mathematical Programming Models for Scheduling Unrelated Parallel Machine with Heterogeneous Delays
One of the main problems in implementing the maintenance actions is the scheduling of the related set of task. This problem could be modelled as an RCPSP, task mapping problem with side constraints or as a load balancing problem. In general it concerns the allocation of a set of task to a set of unrelated resources, that have different capabilities, and with some side constraints like a waiting time, setup time or transition time between tasks execution. Moreover, in real cases, this lag depends on the tasks and the resources. For example, let us consider a set of maintenance action to be conducted on different points on a rail network with limited and nonidentical resources. The transition times or delays between the execution of two consecutively scheduled tasks will depend: (1) on the tasks themselves, the setup and the preparation of the resource depend on the executed or to be executed task; (2) on the resources; the speed of the resource is one of the obvious parameter in this case. We investigate this scheduling problem to study how the exact methods perform. One of the difficulties, which limit the exact method performances for this combinatorial problem, is the disjunctive constraints – the nonoverlapping constraints between tasks assigned to the same resource. We overcome this limit by some result from graph theory and propose a new mathematical model that contains less binary variables and outperforms the existing models. The size of the model is drastically reduced and the solution time is divided by 5 and even more for some cases.
Our contributions are three fold: taking into account the heterogeneous delays in its general form; a slender linear mathematical formulation of the problem that uses a minimum number of variables and constraints; a heuristics integration which improves a solving time of the mathematical model by endowing good cuts and good bounds.
To compare our model with the existing ones, we applied this approach to the case of task scheduling in heterogeneous processors with heterogeneous communication delay. We are able to solve a problem with up to 50 tasks on 8 computing units in few seconds. A benchmark set of data shows the superiority of our model comparing to the existing ones.