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;
Abstract
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.
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
| Title | On the M- Machine Scheduling for Dags with Bounded Number of Maximal Complete Bipartite Subgraphs | Authors | E. M. El-Sherif, M. M. Kouta and B.I. Bayoumi ; Khamis, Soheir | 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 |
Attached Files
| File | Description | Size | Format | |
|---|---|---|---|---|
| On the M-Machine Scheduling.pdf | 368.65 kB | Adobe PDF | View/Open |
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.