Resource leveling in a machine environment

We address resource leveling problems in a machine environment. Given a set of m machines, one or more renewable resources, and a set of n tasks, each assigned to exactly one of the machines. Each task has a processing time, an earliest start time, a deadline, and resource requirements. There are no precedence relations between the tasks. The tasks have to be sequenced on the machines while minimizing a function of the level of resource utilization from each resource over time. We provide various complexity results including a polynomial time algorithm for a one machine special case. We also propose an exact method using various techniques to find optimal or close-to-optimal solutions. The computational experiments show that our exact method significantly outperforms heuristics and a commercial MIP solver.     

Scheduling tasks with exponential duration on unrelated parallel machines

This paper introduces a stochastic scheduling problem. In this problem a directed acyclic graphs (DAG) represents the precedence relations among $m$ tasks that $n$ workers are scheduled to execute. The question is to find a schedule $\Sigma$ such that if tasks are assigned to workers according to $\Sigma$, the expected time needed to execute all the tasks is minimized. The time needed to execute task $t$ by worker $w$ is a random variable expressed by a negative exponential distribution with parameter ${\lambda }_{wt}$ and each task can be executed by more than one worker at a time. In this paper, we will prove that the problem in its general form is NP-hard, but when the DAG width is constant, we will show that the optimum schedules can be found in polynomial time.     

Scheduling multiprocessor tasks with chain constraints

This paper is concerned with a new model in deterministic scheduling theory, where certain tasks may require more than one processor at a time. This model is motivated by several applications of multimicroprocessor systems and it has received much attention in the last years. In the paper it is assumed that each task can be processed on any processor subset of a given task-dependent size. Tasks are nonpreemptable and there are precedence constraints among them. It is proved that the problem of minimizing schedule length is NP-hard for three processors even if all the tasks have unit processing times and precedence constraints form a set of chains. Thus, it is unlikely to be solvable in polynomial time. On the other hand, two low order polynomial-time algorithms are given for the m processor case if processor requirements of the tasks in each chain are either uniform or monotonically decreasing (increasing).     

Robust resource allocations in temporal networks

Temporal networks describe workflows of time-consuming tasks whose processing order is constrained by precedence relations. In many cases, the durations of the network tasks can be influenced by the assignment of resources. This leads to the problem of selecting an ‘optimal’ resource allocation, where optimality is measured by network characteristics such as the makespan (i.e., the time required to complete all tasks). In this paper we study a robust resource allocation problem where the task durations are uncertain, and the goal is to minimise the worst-case makespan. We show that this problem is generically ${\mathcal{NP}}$ -hard. We then develop convergent bounds on the optimal objective value, as well as feasible allocations whose objective values are bracketed by these bounds. Numerical results provide empirical support for the proposed method.     

Parallel dedicated machines scheduling with chain precedence constraints

A set of n nonpreemptive tasks are to be scheduled on m parallel dedicated machines with a regular criterion. Chain precedence constraints among the tasks, deterministic processing times and processing machine of each task are given.     

An approximation algorithm for scheduling trees of malleable tasks

This work presents an approximation algorithm for scheduling the tasks of a parallel application. These tasks are considered as malleable tasks (MT in short), which means that they can be executed on several processors. This model receives recently a lot of attention, mainly due to their practical use for implementing actual parallel applications. Most of the works developed within this model deal with independent MT for which good approximation algorithms have been designed. This work is devoted to the case where MT are linked by precedence relations. We present a 4(1+ϵ) approximation algorithm (for any fixed ϵ) for the specific structure of a tree. This preliminary result should open the way for further investigations concerning arbitrary precedence graphs of MT.     

A minmax regret approach to the critical path method with task interval times

The execution of a given project, with a number of interrelated tasks due to precedence constraints, represents a challenge when one must to control the available resources and the compromised due dates. In this paper, we analyse this problem under uncertain individual task completing times, specifically, we will assume that a given range, for the admissible values of each individual completing time, is available. Taking into account that the precedence relations between tasks must be preserved, each realization of the admissible execution times for the set of tasks will define a new scenario determining the ending time for the project and the subset of critical tasks.     

Scheduling UET task systems with concurrency on two parallel identical processors

Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.     

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.     

Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n≤m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(nmax {m,nlog ² m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n=2 or n=3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.     

A buffer minimization problem for the design of embedded systems

We consider a set of tasks, each of them is composed by a set of sequential operations, and a set of buffers. Each buffer b is defined between two tasks T_i and T_j, and is managed as a FIFO structure. Some operations from T_i write data to the buffer b, others from T_j get data from b.The writings and readings generate precedence constraints between the operations. The limitation of the size of the buffers generates another set of precedence constraints between them and circuits in the precedence graph may appear. In this case, there is no feasible schedule for the operations. The aim is to determine the size of each buffer such that the global surface of the buffers is minimized and there is no circuit in the precedence graph.We prove that this problem is polynomial for two tasks using a flow algorithm. We also prove that it is NP-complete in the strong sense for three tasks.     

An <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">N</Emphasis> log (1/<Emphasis Type="Italic">ɛ</Emphasis>)) Algorithm for the Two-resource Allocation Problem with a Non-differentiable Convex Objective Function

This paper considers a job consisting of N totally ordered tasks. There is a budget for each of the two non-substitutable resources needed for the tasks. The processing time of each task is inversely proportional to the amount of resource allocated. We determine how to distribute the resources to the tasks so that the completion time of the job is minimized. A search procedure is presented that solves the problem with a worst case performance O(N log (1/?)), where ? is a given accuracy.     

The complexity of a cyclic scheduling problem with identical machines and precedence constraints

We consider a set T of tasks with unit processing times. Each of them must be executed infinitely often. A uniform constraint is defined between two tasks and induces a set of precedence constraints on their successive executions. We limit our study to a subset of uniform constraints corresponding to two hypotheses often verified in practice: Each execution of T must end by a special task f, and uniform constraints between executions from different iterations start from f. We have a fixed number of identical machines. The problem is to find a periodic schedule of T which maximizes the throughput. We prove that this problem is NP-hard and show that it is polynomial for two machines. We also present another nontrivial polynomial subcase which is a restriction of uniform precedence constraints.     

Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay

We consider the makespan minimization for a unit execution time task sequencing problem with a bipartite precedence delays graph and a positive precedence delay d. We prove that the associated decision problem is strongly NP-complete and we provide a non-trivial polynomial sub-case. We also give an approximation algorithm with ratio .     

Local search procedures for improving feasible solutions to the sequential ordering problem

Given a digraphG=(V, A), a weight for each node inV and a weight for each arc inA, the Sequential Ordering Problem (SOP) consists of finding a Hamiltonian path, such that a release date and a deadline for each node and precedence relationships among nodes are satisfied and a linear function is minimized. In our case, the objective function is the maximum cumulated potential of the nodes (also, the so-called makespan). The SOP has a broad range of applications, mainly in production planning and manufacturing systems. Nodes represent jobs (to be processed on a single machine), arcs represent sequencing of the jobs, the nodes' weights are the processing time for the jobs, the arcs' weights are the setup times for two consecutive jobs, and the cumulated potential of a node is the completion time of a job. The goal is to produce a feasible scheduling of the jobs so that the makespan is minimized. We present an approximate algorithm for improving feasible solutions to the SOP. The algorithm is based on two local search-opt procedures to reduce the makespan while satisfying the time window (i.e. release date and deadline) and precedence constraints, for=3 and 4. The complexity of the algorithm isO(bn ⁴), wheren denotes the number of nodes andb is the average number of precedences per node. Extensive computational experience and implementation aspects are reported for very large-scale instances up to 3000 nodes and 9000 precedences. Experience with real-life cases is also reported.     

Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap

Coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has a constant exact length and the precedence constraints are strict. Although it is proven that the problem stated above is NP-hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper contains a solution for the problem of coupled tasks scheduling with an assumption that the precedence constraints graph has a form of chains and it presents an algorithm that can solve the problem with such assumption in time O(n?log?n).     

Decentralized list scheduling

Classical list scheduling is a very popular and efficient technique for scheduling jobs for parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors, the cost for managing a single centralized list becomes too prohibitive. A suitable approach to reduce the contention is to distribute the list among the computational units: each processor only has a local view of the work to execute. Thus, the scheduler is no longer greedy and standard performance guarantees are lost. The objective of this work is to study the extra cost that must be paid when the list is distributed among the computational units. We first present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load imbalance between the local lists. We obtain an equation giving the evolution of the potential by computing its expected decrease in one step of the schedule. Our main theorem shows how to solve such equations to bound the makespan. Then, we apply this method to several scheduling problems, namely, for unit independent tasks, for weighted independent tasks and for tasks with precedence constraints. More precisely, we prove that the time for scheduling a global workload W composed of independent unit tasks on m processors is equal to W/m plus an additional term proportional to log₂ W. We provide a lower bound which shows that this is optimal up to a constant. This result is extended to the case of weighted independent tasks. In the last setting, precedence task graphs, our analysis leads to an improvement on the bound of Arora et al. (Theory Comput. Syst. 34(2):115–144, 2001). We end with some experiments using a simulator. The distribution of the makespan is shown to fit existing probability laws. Moreover, the simulations give a better insight into the additive term whose value is shown to be around 3log₂ W confirming the precision of our analysis.     

General scheduling non-approximability results in presence of hierarchical communications

We investigate on the issue of minimizing the makespan (resp. the sum of the completion times) for the multiprocessor scheduling problem in presence of hierarchical communications. We consider a model with two levels of communication: interprocessor and intercluster. The processors are grouped in fully connected clusters. We propose general non-approximability results in the case where all the tasks of the precedence graph have unit execution times, and where the multiprocessor is composed of an unrestricted number of machines with l ? 4 identical processors each.     

Optimal scheduling on parallel machines for a new order class

This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines.     

A lagrangian relaxation and ACO hybrid for resource constrained project scheduling with discounted cash flows

We consider a project scheduling problem where a number of tasks need to be scheduled. The tasks share resources, satisfy precedences, and all tasks must be completed by a common deadline. Each task is associated with a cash flow (positive or negative value) from which a “net present value” is computed dependent upon its completion time. The objective is to maximize the cumulative net present value of all tasks. We investigate (1) Lagrangian relaxation methods based on list scheduling, (2) ant colony optimization and hybrids of (1) and (2) on benchmark datasets consisting of up to 120 tasks. Considering lower bounds, i.e., maximizing the net present value, the individual methods prove to be effective but are outperformed by the hybrid method. This difference is accentuated when the integrality gaps are large.