Two-machine open shop problem with agreement graph - Université de technologie de Troyes Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2019

Two-machine open shop problem with agreement graph

Résumé

This paper addresses the problem of scheduling jobs on a two-machine open shop subject to constraints given by an agreement graph G, such that jobs can be processed simultaneously on different machines if and only if they are represented by adjacent vertices in G. The problem of minimizing the maximum completion time (makespan) is strongly NP-hard for three distinct values of processing times and for G being a bipartite graph. We extend the study presented in [3] and [4] to the proportionate open shop system. We first prove the NP-hardness of the case of two values of processing times and more general agreement graphs which closes definitely the complexity status of the problem. Then, we present some restricted cases that can be solved in polynomial time. We also derive new complexity results of the open shop under resource constraints and of the partition into triangles problem.

Dates et versions

hal-02290537 , version 1 (17-09-2019)

Identifiants

Citer

Nour El Houda Tellache, Mourad Boudhar, Farouk Yalaoui. Two-machine open shop problem with agreement graph. Theoretical Computer Science, 2019, 796, pp.154-168. ⟨10.1016/j.tcs.2019.09.005⟩. ⟨hal-02290537⟩

Collections

CNRS UTT LOSI
48 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More