SCHEDULING JOBS ON IDENTICAL MACHINES WITH SPLIT AGREEMENT GRAPH
Mourad Boudhar, Mohammed Bendraouche
We treat the following problem of scheduling with agreements: a set of jobs must be scheduled non-preemptively on two identical machines under the constraints that only some specific jobs can be scheduled simultaneously on different machines. These constraints are modeled by an agreement graph and the aim is to minimize the makespan. This problem is polynomial when the processing times are either or. We prove that the latter becomes hard when the release dates can take two distinct values and, even for split graphs. We also establish a polynomial result for split graphs when the jobs of the clique have unit processing times and those of the in-dependent set are arbitrary.
Lecture Notes in Management Science (2011) Vol. 3: 523-526
3rd International Conference on Applied Operational Research, Proceedings
© Tadbir Operational Research Group Ltd. All rights reserved.
ISSN 2008-0050 (Print)
ISSN 1927-0097 (Online)
· Literature Review
· Case Arbitrary
· The Jobs Of The Clique Have Unit Processing Time