Name
Abstract | ||
|---|---|---|
The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2 × 2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3 × 3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.dam.2005.04.011 | Discrete Applied Mathematics |
Keywords | Field | DocType |
polynomial time optimization algorithm,max-plus algebra,matrices product,branch-and-bound algorithm,general case,finite number,important number,scheduling,numerous scheduling problem,optimization problem,single machine problem,optimization,two-machine flow shop problem,lower bound,scheduling problem,polynomial time,computer experiment,upper bound,flow shop scheduling,branch and bound algorithm | Mathematical optimization,Combinatorics,Upper and lower bounds,Matrix (mathematics),Flow shop scheduling,co-NP-complete,Triangular matrix,Time complexity,Optimization problem,Mathematics,Covering problems | Journal |
Volume | Issue | ISSN |
154 | 15 | Discrete Applied Mathematics |
Citations | PageRank | References |
9 | 1.19 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J.-L. Bouquard | 1 | 40 | 2.98 |
| Christophe Lenté | 2 | 63 | 6.37 |
| J.-C. Billaut | 3 | 73 | 5.79 |