Name
Abstract | ||
|---|---|---|
We consider the job shop scheduling problem with unit-time operations and the makespan criterion. This problem is reduced to finding an optimal colouring of a special class of mixed graph, where its partial graph without edges represents the union of maximal directed paths and its partial graph without arcs represents the union of maximal cliques. As the problem is known to be NP-hard, both exact and heuristic methods are proposed to solve it. This study is carried out in three steps. First, a new lower and upper bounds for the mixed chromatic number are proposed. Afterwards, a colour-indexed mathematical model using the proposed bounds is developed. Then, a tabu search using a dynamic neighbourhood structure is adapted for solving large instances. Computational experiments conducted on several modified benchmarks show the efficiency and effectiveness of the proposed resolution methods. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1080/00207543.2016.1224950 | INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH |
Keywords | DocType | Volume |
mixed graph colouring, job shop scheduling, lower and upper bounds, mixed integer linear programming, tabu search | Journal | 55 |
Issue | ISSN | Citations |
6 | 0020-7543 | 0 |
PageRank | References | Authors |
0.34 | 14 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ahmed Kouider | 1 | 0 | 0.34 |
| Hacène Ait Haddadène | 2 | 0 | 0.34 |
| Samia Ourari | 3 | 6 | 1.86 |
| Ammar Oulamara | 4 | 17 | 3.89 |