A two-machine no-wait flow shop problem with two competing agents
| Autor: | Djamal Rebaine, Mourad Boudhar, Abdennour Azerine |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
021103 operations research Control and Optimization Branch and bound Job shop scheduling Computer science Applied Mathematics 0211 other engineering and technologies Approximation algorithm 0102 computer and information sciences 02 engineering and technology Flow shop scheduling 01 natural sciences Upper and lower bounds Tabu search Computer Science Applications Computational Theory and Mathematics 010201 computation theory & mathematics Theory of computation Discrete Mathematics and Combinatorics Time complexity |
| Zdroj: | Journal of Combinatorial Optimization. 43:168-199 |
| ISSN: | 1573-2886 1382-6905 |
| Popis: | In this paper, we study the two-machine no-wait flow shop scheduling problem with two competing agents. The objective is to minimize the overall completion time of one agent subject to an upper bound on the makespan of the second agent. We proved the $$\mathcal {NP}$$ -hardness for three special cases: (1) each agent has exactly two operations. (2) the jobs of one agent require processing only on one machine, (3) the no-wait constraint is only required for the jobs of one agent. We exhibited polynomial time algorithms for other restricted cases. We also proposed a mathematical programming model and a branch and bound scheme as solving approaches for small-scale problems. For large instances, we present a tabu search meta-heuristic algorithm. An intensive experimental study is conducted to illustrate the effectiveness of the proposed exact and approximation algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink