Journées de l'optimisation 2014

                             Incluant une Journée industrielle de l'optimisation

                                              HEC Montréal, 5 - 7 mai 2014


HEC Montréal, 5 — 7 mai 2014

Horaire Auteurs Mon horaire

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 Mutli-Objective RCPSP with Budget Optimization

    • Oumar Kone, University Nangui Abrogoua
    • Matthias P. Takouda, prés., Laurentian University
    • Kouassi Hilaire EDI, University Nangui Abrogoua

    We consider Event-based MILP formulations of RCPSP in multi-objective 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, Event-based MILP models for resource-constrained project scheduling problems, Computers & Operations Research, 38(1), p.3-13, 2011.

  • 11h25 - 11h50

    A Tabu Search/Path Relinking Algorithm to Solve the Job Shop Scheduling Problem

    • Zhipeng Lu, prés., Huazhong University of Science and Technology

    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 state-of-the-art 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

    • Abdessamad Ait-El-Cadi, prés., Université de Valenciennes et du Hainaut-Cambrésis
    • Rabie Ben Atitallah, Université de Valenciennes et du Hainaut-Cambrésis
    • Said Hanafi, Universite de Valenciennes et du Hainaut-Cambrésis
    • Nenad Mladenovic, Mathematical Institute SANU
    • Abdelhakim Artiba, Université de Valenciennes et du Hainaut-Cambrésis

    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 non-identical 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 non-overlapping 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.