On the M- Machine Scheduling for Dags with Bounded Number of Maximal Complete Bipartite Subgraphs

E. M. El-Sherif, M. M. Kouta and B.I. Bayoumi ; Khamis, Soheir 


In this paper an upper bound on the number of solutions of m-machine scheduling problem is found, where the precedence relations between the tasks can be represented by a Complete Bipartite Composite, CBC, dag. In fact, a CBC dag represents an N-free partially ordered set. Also a polynomial time algorithm (O(n .k!)) to get an optimal solution is presented, where n is the number of tasks and k is the number of blocks (bounded) of the CBC dag.

Other data

Keywords Scheduling problem, partially ordered sets (posets), Complete Bipartite Composite (CBC) dags, N-free posets, totally-interacted graphs, m-machine, identical processors and NP-complete problem.
Issue Date 25-Nov-1993
Journal The Fifth Conference on Operations Research and its Military 
URI http://research.asu.edu.eg/123456789/1141

File Description SizeFormat 
On the M-Machine Scheduling.pdf368.65 kBAdobe PDFView/Open
Recommend this item

CORE Recommender


Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.