Combinatorial Algorithms Forbatch Scheduling And Network Problems

Optimization is the act of obtaining the best (or optimal) result under given circumstances. Combinatorial optimization is concerned with discrete optimization problems which have a finite number of feasible solutions. In the framework of complexity theory, we want to find the optimum in time that is polynomial in the input size. An algorithm that runs in polynomial time is said to be efficient. An efficient algorithm is called exact (or optimal) if it produces an optimal solution to a problem.In cases when a polynomial time exact algorithm is unlikely to exist (the so-called NP-hard problems), one is constrained to design efficient approximation algorithms that are able to find provably nearly optimal solutions. The approximation ratio (or the performance ratio) of an algorithm, for minimization problems, is defined as the worst-case ratio on any input instance of the problem between the value of the solution proposed by the algorithm and the optimal solution value. For maximization problems the approximation ratio (or the performance ratio) is defined as the worst-case ratio on any input instance of the problem between the optimal solution value and the value of the solution proposed by the algorithm. An algorithm with approximation ratioρis called aρ-approximation algorithm. The approximation ratio is the usual measure for the quality of an approximation algorithm: the smaller the ratio is, the better the approximation algorithm is.A family of algorithms {A_ε} is called a polynomial time approximation scheme (PTAS) if, for each fixedε> 0, the algorithm A_εis a (1 +ε)- approximation algorithm running in time that is polynomial in the input size. Note thatεis a fixed number, and thus the running time may depend upon 1/εin any manner. If the running time is polynomial in 1/εas well, then we have a fully polynomial time approximation scheme (FPTAS). At the state of the art, FPTASs and PTASs are the best results we can obtain for the NP-hard problems and the so-called strongly NP-hard problems, respectively.This thesis develops efficient combinatorial algorithms for some deterministic optimization problems of batch scheduling and networks. Deterministic refers to the scenario in which all parameters of the problem instance are known in advance. More than half of the problems we study are NP-hard. More than half of the algorithms we present are polynomial time approximation schemes, and the others are exact algorithms or constant-ratio approximation algorithms. Brief descriptions of the problems we study and highlights of our results follow.The thesis begins with a motivational chapter. This is followed by two parts—Part I: combinatorial algorithms for batch scheduling problems, consisting of Chapters 2 through 5, and Part II: combinatorial algorithms for network problems, consisting of Chapters 6 through 8.A typical scheduling problem consists of a set of n jobs that are to be executed on a set of m available machines subject to a variety of constraints. The goal is to find an optimal allocation where optimality is defined by some problem dependent objective. The scheduling problems we study fall under the category of batch scheduling, where a machine can process several jobs simultaneously as a batch. Such a machine is called a batch machine. The motivation for batching jobs is a gain in efficiency: it may be cheaper or faster to process jobs in a batch than to process them individually.There are several models of batch scheduling and we are interested in the following burn-in model. We are given a set of n jobs and m identical parallel batch machines. Each job is associated with a processing time which specifies the minimum time needed to process the job on any one of the machines. In addition, each job is associated with a release time before which it cannot be processed. The processing time of a batch is defined as the longest processing time of any job in the batch. The completion time of a batch is equal to its start time plus its processing time. All the jobs in the same batch begin processing at the same time, and are deemed to have the same completion time, namely, the completion time of the batch. Once the processing has begun on a batch, no jobs can be added or removed until the processing is completed. The processing on each batch is continuous, i.e., once the processing on one batch starts, no other batch can be started until the former one is finished. This model is motivated by the problem of scheduling burn-in operations for large scale integrated circuit manufacturing.We analyze two variants of the burn-in model. In the bounded model, the bound B (the maximum number of jobs that can be processed simultaneously on a machine) for each batch size is effective, i.e., B < n. In the unbounded model, there is effectively no limit on the sizes of batches, i.e., B≥n. The unbounded model arises for instance in situations where compositions need to be hardened in kilns, and a kiln is sufficiently large that it does not restrict batch sizes. Note that the special case B = 1 concurs with the classical scheduling model in which a machine can handle no more than one job at a time. Accordingly, the bounded model gives rise to problems that are at least as difficult as their traditional counterparts.We concentrate on the problems with unequal job release times. These problems are much more difficult than their counterparts in which all jobs arrive at the same time. Three scheduling objectives we are concerned with are minimizing total weighted completion time, minimizing maximum lateness, and minimizing makespan. Denote by C_j the completion time of job j in a schedule.In Chapters 2 and 3, we study the problems of minimizing total weighted completion time on identical parallel bounded and unbounded batch machines. Jobs have positive weightsω_j associated with them and total weighted completion time as the name suggests is simplyΣ_jω_jC_j. Both problems are NP-hard and the former is strongly NP-hard. Among the various objective functions in batch scheduling, that of minimizing total weighted completion time has been identified as one of the most vexing problems in the literature. We present the first PTASs for these two problems. We note, with some surprise, that our algorithms seldom use the techniques developed for batch scheduling problems. Instead, we rely on the techniques developed for classical scheduling problems (B = 1).In Chapter 4, we focus on the problem of minimizing maximum lateness on identical parallel bounded batch machines. Each job j is associated with a due date d_j before which it should be ideally completed. The maximum lateness is defined as max_j{C_j—d_j). The problem is strongly NP-hard. We present the first PTAS for it. The techniques can be easily modified to get the first PTAS for the (NP-hard) problem of minimizing maximum lateness on identical parallel unbounded batch machines. When all d_j are equal to zero, the maximum lateness reduces to the makespan, max_jC_j. Hence we also obtain the first PTASs for the problems of minimizing makespan on identical parallel bounded and unbounded batch machines.Chapter 5 examines the problem of minimizing makespan on a single batch machine with non-identical job sizes. Each job j is associated with a size s_j∈(0,1]. The batch machine can process a number of jobs simultaneously as a batch as long as the total size of jobs in the batch does not exceed 1. Scheduling with non-identical job sizes is a general version of batch scheduling. Clearly, we need not to consider the unbounded model here. Makespan, as mentioned above, is defined as the maximum completion time of all jobs in a schedule. We present a (2 +ε)-approximation algorithm for this problem, whereε> 0 can be made arbitrarily small. The overall running time of our algorithm is O(nlogn) + f(1/ε), where the multiplicative constant hidden in O(n log n) is reasonably small and independent of c. Note that if all jobs are released at the same time and have identical processing times then the problem is just the classical one-dimensional bin packing problem. The bin packing problem is strongly NP-hard and an efficient algorithm that can achieve a better approximation ratio than 3/2 is unlikely to exist.In addition to batch scheduling problems, we also study several optimization problems arising in communication networks. Due to the ever-increasing importance of communication networks for our society and economy, optimization problems concerning the design and efficient operation of such networks are receiving considerable attention in the research community. Aside from their numerous practical applications, network problems also have many interesting methodological characteristics. We focus on ring networks. The ring is a popular topology for communication networks and has attracted much research attention.In Chapter 6, we consider the problem of call admission control in undirected and directed ring networks. Given a ring (undirected or directed) and a set of communication requests. Each request is represented by a pair of nodes (unordered or ordered), and associated with a profit. To satisfy a request in the undirected ring, we need to determine a path between the two nodes of the request in the ring. To satisfy a request in the directed ring, we need to determine a directed path from the source to the destination of the request in the directed ring. The goal of the call admission control problem is to determine and satisfy a maximum profit subset of the requests such that for every (undirected or directed) edge of the (undirected or directed) ring, the number of satisfied requests that are routed through the edge does not exceed the capacity of the edge. We present the first PTASs for both the undirected and directed cases.In Chapter 7, we study the problem of maximizing profits in multifiber WDM networks. To satisfy a set of requests in a multifiber WDM network, we need to assign a path and a wavelength for each request such that on any link the number of any wavelength used does not exceed the number of fibers. Given a multifiber WDM network with a limited number of wavelengths and a set of requests, the problem of maximizing profits is to determine a subset of requests with the maximum profit that can be satisfied in the network. Note that the call admission control problem studied in Chapter 6 is just the special case of this problem with only one wavelength. We focus on chains and rings. For chains, we present a polynomial time exact algorithm. The problem for rings is NP-hard even when all profits are 1. We present two algorithms with approximation ratios 2 and 1.582 +εrespectively, whereε> 0 can be made arbitrarily small. We also consider the uniform variant in rings where all edges have the same number of fibers and give a 1.582-approximation algorithm. These results can be adapted to directed chains and rings as well. When the 2-approximation algorithm for rings is generalized to the directed rings, we require that there exists a link whose two directed edges are respectively the directed edges with minimum capacity in clockwise and counterclockwise directions.Finally, in Chapter 8 we introduce the problem of k-coloring of t-intervals in a cycle, which generalizes several well known optimization problems arising in WDM ring networks. Cycles represent ring networks, colors represent wavelengths, and t-intervals represent requests from clients. Each t-interval consists of up to t (t≥ 1) intervals on the given cycle. The two ends of each interval are the nodes of the cycle. To satisfy a request, one of the intervals defining it must be selected and assigned one of k colors. No intervals selected for the requests can be assigned the same color if they share an edge of the cycle, otherwise wavelength collision will occur. Given a cycle, k colors and a set of requests ( t-intervals), the goal is to satisfy a maximum number of requests. We present a 3.042-approximation algorithm for this problem. In the process we also obtain a 2.542-approximation algorithm for the problem of k-coloring of t-intervals in a chain.