SCHEDULING JOBS ON IDENTICAL MACHINES WITH SPLIT AGREEMENT GRAPH

 

Mourad Boudhar, Mohammed Bendraouche

 

Abstract

 

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.

www.tadbir.ca

 

ISSN 2008-0050 (Print)

ISSN 1927-0097 (Online)

 

ARTICLE OUTLINE

 

·         Introduction

·         Literature Review

·         Case Arbitrary

·         The Jobs Of The Clique Have Unit Processing Time

·         Conclusion

·         References

 

Full Text PDF