Displaying similar documents to “France Telecom workforce scheduling problem: a challenge”

Large neighborhood improvements for solving car sequencing problems

Bertrand Estellon, Frédéric Gardi, Karim Nouioua (2006)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

The 𝒩 P -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...

Adaptive search heuristics for the generalized assignment problem.

Helena Ramalhinho Lourenço, Daniel Serra (2002)

Mathware and Soft Computing

Similarity:

The Generalized Assignment Problem consists of assigning a set of tasks to a set of agents at minimum cost. Each agent has a limited amount of a single resource and each task must be assigned to one and only one agent, requiring a certain amount of the agent's resource. We present the application of a MAX-MIN Ant System (MMAS) and a greedy randomized adaptive search procedure (GRASP) to the generalized assignment problem based on hybrid approaches. The MMAS heuristic can be seen as an...

Reservation table scheduling: branch-and-bound based optimization . integer linear programming techniques

Hadda Cherroun, Alain Darte, Paul Feautrier (2007)

RAIRO - Operations Research

Similarity:

The recourse to operation research solutions has strongly increased the performances of scheduling task in the High-Level Synthesis (called hardware compilation). Scheduling a whole program is not possible as too many constraints and objectives interact. We decompose high-level scheduling in three steps. Step 1: Coarse-grain scheduling tries to exploit parallelism and locality of the whole program (in particular in loops, possibly imperfectly nested) with a rough view of the target...

Incorporating the strength of MIP modeling in schedule construction

Cor A.J. Hurkens (2009)

RAIRO - Operations Research

Similarity:

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...

Consistency checking within local search applied to the frequency assignment with polarization problem

Michel Vasquez, Audrey Dupont, Djamal Habet (2003)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

We present a hybrid approach for the Frequency Assignment Problem with Polarization. This problem, viewed as Max-CSP, is treated as a sequence of decision problems, CSP like. The proposed approach combines the Arc-Consistency techniques with a performed Tabu Search heuristic. The resulting algorithm gives some high quality solutions and has proved its robustness on instances with approximately a thousand variables and nearly ten thousand constraints.

Scheduling multiprocessor tasks on two parallel processors

Jacek Błażewicz, Paolo Dell'Olmo, Maciej Drozdowski (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.