Implantation et complexité des techniques de programmation dynamique dans les méthodes de confection de tournées et d'horaires
Incorporating the strength of MIP modeling in schedule construction
Linear programming techniques can be used in constructing schedules but their application is not trivial. This in particular holds true if a trade-off has to be made between computation time and solution quality. However, it turns out that – when handled with care – mixed integer linear programs may provide effective tools. This is demonstrated in the successful approach to the benchmark constructed for the 2007 ROADEF computation challenge on scheduling problems furnished by France Telecom.
Introduction de dates échues dans l'analyse PERT-coût
Knowledge based and CP-driven approach applied to multi product small-size production flow
Large neighborhood improvements for solving car sequencing problems
The -hard problem of car sequencing has received a lot of attention these last years. Whereas a direct approach based on integer programming or constraint programming is generally fruitless when the number of vehicles to sequence exceeds the hundred, several heuristics have shown their efficiency. In this paper, very large-scale neighborhood improvement techniques based on integer programming and linear assignment are presented for solving car sequencing problems. The effectiveness of this approach...
Large neighborhood improvements for solving car sequencing problems
The NP-hard problem of car sequencing has received a lot of attention these last years. Whereas a direct approach based on integer programming or constraint programming is generally fruitless when the number of vehicles to sequence exceeds the hundred, several heuristics have shown their efficiency. In this paper, very large-scale neighborhood improvement techniques based on integer programming and linear assignment are presented for solving car sequencing problems. The effectiveness of this approach...
Les problèmes de tournées avec contraintes de fenêtres de temps, l'état de l'art
Les problèmes d'ordonnancement de type «flow-shop» hybride : état de l'art
Les problèmes d'ordonnancement de type flow-shop hybride : état de l'art
A special class of scheduling problems is studied in this paper, named Hybrid Flowshop, n jobs have to be performed in a shop and each of them has the same routing (so this is a flowshop). A job consists in k different operations. A set of machines are able to perform each operation and this set is called a stage. So when a job consists in two operations, there are two stages in the shop. After introducing the scheduling generalities, we define our preocupations and we propose a notation in...
Les tables de réservation numériques : un outil pour la résolution de certains problèmes d'ordonnancement cycliques
Location of polygon vertices on circles and its application in transport studies
The paper deals with the problem how to locate a set of polygon vertices on given circles fulfilling some criteria of "regularity" of individual and composed polygons. Specifying the conditions we can obtain a lot of particular versions of this general problem. Some of them are already solved, the others are not. Applications of this theory can be found in scheduling of periodically repeating processes, e.g. in coordination of several urban lines on a common leg, in optimization of the rhythm of...
Lower bounds for the scheduling problem with uncertain demands
This paper proposes various lower bounds to the makespan of the flexible job shop scheduling problem (FJSP). The FJSP is known in the literature as one of the most difficult combinatorial optimisation problems (NP-hard). We will use genetic algorithms for the optimisation of this type of problems. The list of the demands is divided in two sets: the actual demand, which is considered as certain (a list of jobs with known characteristics), and the predicted demand, which is a list of uncertain jobs....
Managing a patient waiting list with time-dependent priority and adverse events
This paper addresses the problem of managing a waiting list for elective surgery to decide the number of patients selected from the waiting list and to schedule them in accordance with the operating room capacity in the next period. The waiting list prioritizes patients not only by their initial urgency level but also by their waiting time. Selecting elective surgery patients requires a balance between the waiting time for urgent patients and that for less urgent patients. The problem is formulated...
Mathematical solutions for solving periodic railway transportation.
Maximization of distances of regular polygons on a circle
This paper presents the solution of a basic problem defined by J. Černý which solves a concrete everyday problem in railway and road transport (the problem of optimization of time-tables by some criteria).
Méthode heuristique pour le problème de flow shop hybride avec machines dédiées
Dans ce papier, nous traitons le problème de minimisation du makespan dans un flow shop hybride à deux étages avec machines dédiées. En premier lieu, nous présentons des propriétés de base, un ensemble de bornes inférieures et deux cas polynomiaux. En second lieu, nous proposons une nouvelle heuristique qui exploite ces propriétés, et cherche à placer les jobs, en tenant compte pour chaque instance du problème, de la valeur de la borne inférieure. La dernière partie de ce travail présente les résultats expérimentaux...
Minimizing maximum lateness in two-stage projects by tropical optimization
We are considering a two-stage optimal scheduling problem, which involves two similar projects with the same starting times for workers and the same deadlines for tasks. It is required that the starting times for workers and deadlines for tasks should be optimal for the first-stage project and, under this condition, also for the second-stage project. Optimality is measured with respect to the maximal lateness (or maximal delay) of tasks, which has to be minimized. We represent this problem as a...
Minimizing the earliness and tardiness cost of a sequence of tasks on a single machine
Assume that tasks must be processed by one machine in a fixed sequence. The processing time, the preferred starting time and the earliness and tardiness costs per time unit are known for each task. The problem is to allocate each task a starting time such that the total cost incurred by the early and tardy tasks is minimum. Garey et al. have proposed a nice algorithm for the special case of symmetric and task-independent costs. In this paper we first extend that algorithm to the case of asymmetric...
Minimizing the Earliness and Tardiness Cost of a Sequence of Tasks on a Single Machine
Assume that n tasks must be processed by one machine in a fixed sequence. The processing time, the preferred starting time and the earliness and tardiness costs per time unit are known for each task. The problem is to allocate each task a starting time such that the total cost incurred by the early and tardy tasks is minimum. Garey et al. have proposed a nice O(nlogn) algorithm for the special case of symmetric and task-independent costs. In this paper we first extend that algorithm to the...
Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds
This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Preemption is not allowed. The objective is to find a feasible job sequence that minimizes the number of tardy jobs. On the basis of an original mathematical integer programming formulation, this paper shows how good-quality lower and upper bounds can be computed. Numerical experiments are provided for assessing the proposed approach.