Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results

Jean Damay; Alain Quilliot; Eric Sanlaville

The search session has expired. Please query the service again.

Displaying similar documents to “Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results”

Airspace sectorization with constraints

Huy Trandac, Philippe Baptiste, Vu Duong (2005)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

We consider the Airspace Sectorization Problem (ASP) in which airspace has to be partitioned into a given number of sectors, each of which being assigned to a team of air traffic controllers. The objective is to minimize the coordination workload between adjacent sectors while balancing the total workload of controllers. Many specific constraints, including both geometrical and aircraft related constraints are taken into account. The problem is solved in a constraint programming framework....

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

Single machine preemptive scheduling to minimize the weighted number of late jobs with deadlines and nested release/due date intervals

Valery S. Gordon, F. Werner, O. A. Yanushkevich (2001)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

This paper is devoted to the following version of the single machine preemptive scheduling problem of minimizing the weighted number of late jobs. A processing time, a release date, a due date and a weight of each job are given. Certain jobs are specified to be completed in time, i.e., their due dates are assigned to be deadlines, while the other jobs are allowed to be completed after their due dates. The release/due date intervals are nested, i.e., no two of them overlap (either they...

Partially clairvoyant scheduling for aggregate constraints.

Subramani, K. (2005)

Journal of Applied Mathematics and Decision Sciences

Similarity:

An $0 (n^{3})$ worst case bounded special $L P$ knapsack $(0 - 1)$ with two constraints

Ruy E. Campello, Nelson Maculan (1988)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Enumerating the Set of Non-dominated Vectors in Multiple Objective Integer Linear Programming

John Sylva, Alejandro Crema (2008)

RAIRO - Operations Research

Similarity:

An algorithm for enumerating all nondominated vectors of multiple objective integer linear programs is presented. The method tests different regions where candidates can be found using an auxiliary binary problem for tracking the regions already explored. An experimental comparision with our previous efforts shows the method has relatively good time performance.

Managing cost uncertainties in transportation and assignment problems.

Adlakha, V., Arsham, H. (1998)

Journal of Applied Mathematics and Decision Sciences

Similarity:

An algorithm for solving multiple objective integer linear programming problem

Moncef Abbas, Djamal Chaabane (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In the present paper a complete procedure for solving Multiple Objective Integer Linear Programming Problems is presented. The algorithm can be regarded as a corrected form and an alternative to the method that was proposed by Gupta and Malhotra. A numerical illustration is given to show that this latter can miss some efficient solutions. Whereas, the algorithm stated bellow determines all efficient solutions without missing any one.

A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem

Matic, Dragan (2012)

Serdica Journal of Computing

Similarity:

This paper presents a Variable neighbourhood search (VNS) approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational...