Task scheduling with and without communication delays: A unified approach

The problem of scheduling directed acyclic task graphs on an unbounded number of processors is considered. We present a single algorithm which is applicable to several special cases, thus effecting a unified approach to task scheduling independent of the task graph. We start by considering multi-stage dags and present an algorithm that computes a schedule in O(Nq log q) time, where N is the number of stages, and q is the maximum number of edges between any two stages of the graph. We show that the schedule produced by the algorithm is optimal when: (i) all communication delays are zero or, (ii) the precedence graph is an in-tree or an out-tree and communication times are small or, (iii) the task graph is densely connected and communication costs and processing costs are unity. For multi-stage dags with small communication times we show that the makespan of the schedule generated by our algorithm is less than twice that of the optimal. We also bound the makespan for the case when communication times are arbitrary. We then show how the algorithm may be applied to schedule arbitrary dags and derive the performance bounds for this case. Finally, we present the results of tests we carried out with randomly generated task graphs. These seem to indicate that, on the average, the algorithm performs substantially better than theoretical worst case predictions.     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

Optimal assignment of task modules with precedence for distributed processing by graph matching and state-space search

A graph matching approach to optimal assignment of task modules with varying lengths and precedence relationship in a distributed computing system is proposed. Inclusion of module precedence into the optimal solution is made possible by the use of topological module orderings. Two graphs are defined to represent the processor structure and the module precedence relationship, respectively. Assignment of the task modules to the system processors is transformed into a type of graph matching. The search of optimal graph matching corresponding to optimal task assignment is formulated as a state-space search problem which is then solved by theA* algorithm in artificial intelligence. Illustrative examples and experimental results are included to show the effectiveness of the proposed approach.     

A minimization version of a directed subgraph homeomorphism problem

We consider a special case of the directed subgraph homeomorphism or topological minor problem, where the host graph has a specific regular structure. Given an acyclic directed pattern graph, we are looking for a host graph of minimal height which still allows for an embedding. This problem has applications in compiler design for certain coarse-grain reconfigurable architectures. In this application domain, the task is to simultaneously schedule, bind and route a so-called data-flow graph, where vertices represent operations and arcs stand for data dependencies between the operations, given an orthogonal grid structure of reconfigurable processing elements (PEs) that have restricted communication abilities. We show that the problem of simultaneously scheduling, binding and routing is NP-complete by describing a logic engine reduction from NAE-3-SAT. This result holds even when the input graph is a directed tree with maximum indegree two. We also give a |V|^3/2-approximation algorithm. J. A. Brenner’s research supported by the DFG Research Center Matheon “Mathematics for key technologies”. J. C. van der Veen’s research supported by DFG Focus Program 1148, “Reconfigurable Architectures”, Grants FE 407/8-1 and FE 407/8-2.     

A tabu search tutorial based on a real-world scheduling problem

We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of the algorithm can be reduced drastically from O(n ³) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders).     

Approximations for the Two-Machine Cross-Docking Flow Shop Problem

We consider in this article the Two-Machine Cross-Docking Flow Shop Problem, which is a special case of scheduling with typed tasks, where we have two types of tasks and one machine per type. Precedence constraints exist between tasks, but only from a task of the first type to a task of the second type. The precedence relation is thus a directed bipartite graph. Minimizing the makespan is strongly NP-hard even with unit processing times, but any greedy method yields a 2-approximation solution. In this paper, we are interested in establishing new approximability results for this problem. More specifically, we investigate three directions: list scheduling algorithms based on the relaxation of the resources, the decomposition of the problem according to the connected components of the precedence graph, and finally the search of the induced balanced subgraph with a bounded degree.     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

Graph models for scheduling systems with machine saturation property

Let be a set of n independent tasks and a set of m processors. During each time instant, each processor can be used by a single task at most. A schedule is for each task an allocation of one or more time intervals to one or more processors. A schedule is said to be optimal if it minimizes the maximum completion time. We say a schedule S has the machine saturation property (MS property) if, at any time instant of task execution, all the machines are simultaneously busy. In this paper, we analyze the conditions under which a parallel scheduling system allows a schedule with the MS property. While for some simple models the analytical conditions can be easily stated, a graph model approach is required when conflicts of processor usage are present. For this reason, we define the class of saturated graphs that correspond to scheduling systems with the MS property. We present efficient graph recognition algorithms to verify the MS property directly on some classes of saturated graphs     

An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs

The maximum weight k-independent set problem has applications in many practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design layout and routing problem. Based on DAG (Directed Acyclic Graph) approach, an O(kn ²) time sequential algorithm is designed in this paper to solve the maximum weight k-independent set problem on weighted trapezoid graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph.     

On-line k-Truck Problem and Its Competitive Algorithms

In this paper, based on the Position Maintaining Strategy (PMS for short), on-line scheduling of k-truck problem, which is a generalization of the famous k-server problem, is originally presented by our team. We proposed several competitive algorithms applicable under different conditions for solving the on-line k-truck problem. First, a competitive algorithm with competitive ratio 2k+1/ is given for any 1. Following that, if (c+1)/(c-1) holds, then there must exist a (2k-1)-competitive algorithm for k-truck problem, where c is the competitive ratio of the on-line algorithm about the relevant k-server problem. And then a greedy algorithm with competitive ratio 1+/, where lambda is a parameter related to the structure property of a given graph, is given. Finally, competitive algorithms with ratios 1+1/ are given for two special families of graphs.     

A subproblem-centric model and approach to the nurse scheduling problem

The number of hospitals in Japan exceeds 10,000, and every month nurses are scheduled to shifts in about 30,000 units in total. There is serious demand for automating this scheduling task. In this paper, we introduce a mathematical programming formulation of the nurse scheduling problem in Japan, and develop a meta-heuristic approach to solve the problem. This scheduling problem is a hard combinatorial problem due to tight constraints involving such factors as the skill level of a team, the need to balance workload among nurses, and the consideration of nurses' preferences, even though the number of the nurses to be scheduled is not large, at between 20 and 40. The performance of our approach is demonstrated by the successful solution of data taken from actual scheduling problems. The proposed model and approach can be adapted for the majority of hospitals in Japan, as well as for some hospitals in other countries, and is likely applicable to many other scheduling problems in the fields of business and logistics. Key words.nurse scheduling – block-angular problem – subproblem – integer programming – relaxation – tabu search – branch-and-boundMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Algorithms for graph partitioning on the planted partition model

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l‐partition problem and we analyze it on a random “planted l‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n^−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−n^Θ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001     

Results on <Emphasis Type="Italic">F</Emphasis>-continuous graphs

For any nontrivial connected graph F and any graph G, the F-degree of a vertex v in G is the number of copies of F in G containing v. G is called F-continuous if and only if the F-degrees of any two adjacent vertices in G differ by at most 1; G is F-regular if the F-degrees of all vertices in G are the same. This paper classifies all P ₄-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph F other than the star K _1,k , k ⩾ 1, there exists a regular graph that is not F-continuous. If F is 2-connected, then there exists a regular F-continuous graph that is not F-regular.      

A Characterization of Graphs without Even Factors

In this paper, we first reduce the problem of finding a minimum parity (g,f)-factor of a graph G into the problem of finding a minimum perfect matching in a weighted simple graph G*. Using the structure of G*, a necessary and sufficient condition for the existence of an even factor is derived. This paper was accomplished while the second author was visiting the Center for Combinatorics, Nankai University. The research is supported by NSFC     

On the geometry,preemptions and complexity of multiprocessor and shop scheduling

In this paper we study multiprocessor and open shop scheduling problems from several points of view. We explore a tight dependence of the polynomial solvability/intractability on the number of allowed preemptions. For an exhaustive interrelation, we address the geometry of problems by means of a novel graphical representation. We use the so-called preemption and machine-dependency graphs for preemptive multiprocessor and shop scheduling problems, respectively. In a natural manner, we call a scheduling problem acyclic if the corresponding graph is acyclic. There is a substantial interrelation between the structure of these graphs and the complexity of the problems. Acyclic scheduling problems are quite restrictive; at the same time, many of them still remain NP-hard. We believe that an exhaustive study of acyclic scheduling problems can lead to a better understanding and give a better insight of general scheduling problems. We show that not only acyclic but also a special non-acyclic version of periodic job-shop scheduling can be solved in polynomial (linear) time. In that version, the corresponding machine dependency graph is allowed to have a special type of the so-called parti-colored cycles. We show that trivial extensions of this problem become NP-hard. Then we suggest a linear-time algorithm for the acyclic open-shop problem in which at most m−2 preemptions are allowed, where m is the number of machines. This result is also tight, as we show that if we allow one less preemption, then this strongly restricted version of the classical open-shop scheduling problem becomes NP-hard. In general, we show that very simple acyclic shop scheduling problems are NP-hard. As an example, any flow-shop problem with a single job with three operations and the rest of the jobs with a single non-zero length operation is NP-hard. We suggest linear-time approximation algorithm with the worst-case performance of ( , respectively) for acyclic job-shop (open-shop, respectively), where (‖ℳ‖, respectively) is the maximal job length (machine load, respectively). We show that no algorithm for scheduling acyclic job-shop can guarantee a better worst-case performance than . We consider two special cases of the acyclic job-shop with the so-called short jobs and short operations (restricting the maximal job and operation length) and solve them optimally in linear time. We show that scheduling m identical processors with at most m−2 preemptions is NP-hard, whereas a venerable early linear-time algorithm by McNaughton yields m−1 preemptions. Another multiprocessor scheduling problem we consider is that of scheduling m unrelated processors with an additional restriction that the processing time of any job on any machine is no more than the optimal schedule makespan C _max^*. We show that the (2m−3)-preemptive version of this problem is polynomially solvable, whereas the (2m−4)-preemptive version becomes NP-hard. For general unrelated processors, we guarantee near-optimal (2m−3)-preemptive schedules. The makespan of such a schedule is no more than either the corresponding non-preemptive schedule makespan or max {C _max^*,p _max}, where C _max^* is the optimal (preemptive) schedule makespan and p _max is the maximal job processing time. E.V. Shchepin was partially supported by the program “Algebraical and combinatorial methods of mathematical cybernetics” of the Russian Academy of Sciences. N. Vakhania was partially supported by CONACyT grant No. 48433.     

Mutual exclusion scheduling with interval graphs or related classes: Complexity and algorithms

This note summarizes the main results presented in the author's Ph.D. thesis, supervised by Professor Michel Van Caneghem and defended on 14th June 2005 at University of Aix-Marseille II, France. The thesis, written in French, is available at http: //www.lif-sud.univ-mrs.fr/Rapports/25-2005.html. The mutual exclusion scheduling problem has an elegant graph-theoretic formulation: given an undirected graph G and an integer k, find a minimum coloring of G such that each color appears at most k times. When G is an interval graph, this problem has some applications in workforce planning. Then, the object of the thesis is to study the complexity of mutual exclusion scheduling problem for interval graphs and related classes. Received: August 2005 / Revised version: September 2005 Frédéric Gardi: On leave from Laboratoire d'Informatique Fondamentale - CNRS UMR 6166, Parc Scientifique et Technologique de Luminy, Marseille, France.     

Scheduling unit — time tasks on flow — shops under resource constraints

We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log ₂ ² n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

A decomposition approach for a very large scale optimal diversity management problem

This paper focuses on the solution of the optimal diversity management problem formulated as a p-Median problem. The problem is solved for very large scale real instances arising in the car industry and defined on a graph with several tens of thousands of nodes and with several millions of arcs. The particularity is that the graph can consist of several non connected components. This property is used to decompose the problem into a series of p-Median subproblems of a smaller dimension. We use a greedy heuristic and a Lagrangian heuristic for each subproblem. The solution of the whole problem is obtained by solving a suitable assignment problem using a Branch-and-Bound algorithm.Received: June 2004 / Revised version: December 2004MSC classification: 49M29, 90C06, 90C27, 90C60All correspondence to: Antonio SforzaIgor Vasilev: Support for this author was provided by NATO grant CBP.NR.RIG.911258.