This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation...
In this paper we consider the problem of scheduling, on a two-machine flowshop, a set of unit-time operations subject to time delays with respect to the makespan. This problem is known to be x1d4a9;x1d4ab; -hard in the strong sense. We propose an algorithm based on a branch and bound enumeration scheme. This algorithm includes the implementation of new lower and upper bound procedures, and dominance rules. A computer simulation to measure the performance of the algorithm is provided for a wide...
This paper is concerned with scheduling when the data are not fully known
before the execution. In that case computing a complete schedule off-line
with estimated data may lead to poor performances. Some flexibility must be
added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization
scheme. This is applied to the m machine problem with communication
delays: in our model an estimation...
The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The...
The notion of treewidth is of considerable interest
in relation to NP-hard problems.
Indeed, several studies have shown that the tree-decomposition method
can be used to solve many basic optimization problems in polynomial
time when treewidth is bounded, even if, for arbitrary graphs, computing
the treewidth is NP-hard.
Several papers present heuristics with computational experiments.
For many graphs the discrepancy between the heuristic results
and the best lower bounds is still very large....
Download Results (CSV)