We consider the problem of scheduling multi-task jobs on identical machines in parallel.Each multi-task job consists of one or more tasks.Each job has a release date and a due date.A task of a job can be processed by any one of the machines.Multiple machines can process the tasks of a job concurrently.The completion time of a job is the time at which all its individual tasks have been completed.A job is late if it is completed after its due date.We study the problem of minimizing the total number of late jobs.We show that while some special cases are solvable, the general problem is NP-hard and there exists no polynomial time ρ-approximation algorithm, for any ρ > 1.We present a general algorithm for the problem and derive from it six heuristics whose performance is evaluated by experimental results.

We study the problem of minimizing total completion time in 2-stage flowshop with availability constraint.This problem is NP-hard in the strong sense even if both machines are always available.With availability constraint, although a bulk of research papers have studied the makespan minimization problem, there is no research done on the total completion time minimization.This paper is the first attempt to tackle this problem.We focus on the case that there is a single unavailable interval on the first machine only.We show that several special cases can be solved optimally or approximated within a constant factor.For the general case, we develop some lower bounds and dominance rules.Then we design and implement a branch and bound algorithm.We investigate the effectiveness of different lower bounds and the dominance rules by computational experiments.We also study how the start time and the duration of the unavailable interval affects the efficiency of the branch and bound algorithm.

We consider scheduling problems in the master-slave model. In this model, each job has to be processed sequentially in three stages. In the first stage, a preprocessing task runs on a master machine, in the second stage, a slave task runs on a dedicated slave machine, and, in the last stage, a postprocessing task again runs on a master machine, possibly different from the master machine in the first stage. It has been shown that the problem of minimizing the makespan or the sum of completion times is NP-hard in the strong sense even if preemption is allowed. In this paper, we design efficient approximation algorithms to minimize the sum of completion times in various settings. These are the first general results for the minsum problem in the master-slave model. We also show that these algorithms generate schedules with small makespan as well

We present two new results about vertex and edge fault-tolerant spanners in Euclidean spaces.We describe the first construction of vertex and edge fault-tolerant spanners having optimal bounds for maximum degree and total cost. We present a greedy algorithm that for any t > 1 and any non-negative integer k, constructs a k-fault-tolerant t-spanner in which every vertex is of degree O(k) and whose total cost is O(k2) times the cost of minimum spanning tree; these bounds are asymptotically optimal.Our next contribution is an efficient algorithm for constructing good fault-tolerant spanners. We present a new, sufficient condition for a graph to be a k-fault-tolerant spanner. Using this condition, we design an efficient algorithm that finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bounds for the total cost.