首页 | 本学科首页   官方微博 | 高级检索  
     


Scheduling: Agreement graph vs resource constraints
Authors:Mohamed Bendraouche  Mourad Boudhar  Ammar Oulamara
Affiliation:1. Faculty of Sciences, Saad Dahleb University, Route de Soumaa, BP 270, Blida, Algeria;2. RECITS Laboratory, USTHB University, BP 32 El-Alia, Bab-Ezzouar, Algiers, Algeria;3. Loria Laboratory, University of Lorraine, Nancy, France
Abstract:We investigate two scheduling problems. The first is scheduling with agreements (SWA) that consists in scheduling a set of jobs non-preemptively on identical machines in a minimum time, subject to constraints that only some specific jobs can be scheduled concurrently. These constraints are represented by an agreement graph. We extend the NP-hardness of SWA with three distinct values of processing times to only two values and this definitely closes the complexity status of SWA on two machines with two fixed processing times. The second problem is the so-called resource-constrained scheduling. We prove that SWA is polynomially equivalent to a special case of the resource-constrained scheduling and deduce new complexity results of the latter.
Keywords:Scheduling   Complexity theory   Identical machines   Agreement graph   Resource constraints
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号