On the M- Machine Scheduling for Dags with Bounded Number of Maximal Complete Bipartite SubgraphsE. M. El-Sherif, M. M. Kouta and B.I. Bayoumi ; Khamis, Soheir
AbstractIn 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.
|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|
Recommend this item
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.