批调度与网络问题的组合算法
|
摘要
优化是根据现状采取行动以获得最好(或最优)的结果，组合最优化研究的是可行解数目有限的离散优化问题。在复杂性理论的框架下，我们希望能在输入规模的多项式时间之内找到最优解，运行在多项式时间之内的算法称为有效算法，输出最优解的有效算法称为精确(或最优)算法。
当多项式时间精确算法很可能不存在时(所谓的NP难解问题)，我们转而设计有效的近似算法以得到次优解，对于极小化问题，算法的近似比(性能比)定义为算法给出的解的目标值与最优值之间的最坏情形比，对于极大化问题，算法的近似比(性能比)定义为最优值与算法给出的解的目标值之间的最坏情形比，近似比为ρ的算法称为ρ-近似算法。通常用近似比来衡量算法的性能，近似比越小，算法越好，
一族算法{A_ε}称为一个多项式时间近似方案(PTAS)，如果对于每一个给定的正数ε，算法A_ε是一个运行于输入规模的多项式时间之内的(1+ε)-近似算法。注意到ε是给定的，因此算法的运行时间可以以任意方式依赖于1／ε。如果运行时间也是1／ε的多项式，我们就得到了全多项式时间近似方案(FPTAS)。对于NP难解问题和所谓的强NP难解问题来说，全多项式时间近似方案和多项式时间近似方案分别是我们目前所能得到的最好结果。
本文研究批调度和网络中的若干确定性优化问题，给出了有效的组合算法。确定性是指问题实例的所有参数均事先已知，我们研究的问题大多是NP难解的，所给出的算法大多是多项式时间近似方案，其余的是精确算法或常数近似比算法。下面简略地描述所研究的问题，并给出主要结果和创新点。
论文第一章介绍了研究的缘起和背景，第二章至第五章是第一部分，给出了若干批调度问题的组合算法；第六章至第八章是第二部分，给出了若干网络问题的组合算法。
一个典型的调度问题包含n个工件和m台机器，在满足一定约束条件下，要将工件安排在机器上进行加工。目标是找到一个最优的安排，最优性由依赖于问题的目标函数所定义。本文研究分批调度问题，每台机器可以同时加工若干个工件，这些工件构成一个批次，这样的机器称为批机器。将工件分批加工是为了提高效率，分批加工比一个一个加工更快或成本更低。
批调度问题有多种模式，本文研究如下的煅烧模式。给定n个工件和m台并行同型批机器，每个工件有一个加工时间，描述了在任意一台机器上加工该工件所需要的最短时间。每个工件还有一个释放时间，在该时间之前不能开始加工这个工件，一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者。一个批次的完工时间等于它的开工时间加上它的加工时间，同一批次中的所有工件有相同的开工时间，也有相同的完工时间，即该批次的完工时间。一个批次从开始加工到完工，不允许向内添加工件或向外移除工件。每个批次的加工都是连续进行的，即：从开工到完工，没有其他批次可以在同一台机器上加工，煅烧模式起源于大规模集成电路生产过程中的煅烧操作调度问题。
煅烧模式分为两类，有界模式：每个批次最多可容纳的工件数目(批容量)B小于工件的总数目n，B表示任一台机器能同时加工的工件的最大数目。无界模式：每个批次可容纳的工件数目没有限制，即B≥n，无界模式的一个例子：在干燥炉中硬化一些化合物，干燥炉足够大因此批容量没有限制。注意有界模式中B=1的情形，就是经典的调度问题(每台机器在任一时间至多加工一个工件)，因此，有界模式的批调度问题，难度不低于经典的调度问题。
集中研究工件释放时间不相同的调度问题，这比所有工件同时到达的问题要难得多，研究三种调度目标：极小化加权完工时间和、极小化最大延迟、极小化最大完工时间，记工件j在一个调度中的完工时间为C_j。
在第二章和第三章，我们研究极小化加权完工时间和的有界批机器和无界批机器并行调度问题，每个工件j有正权w_j。加权完工时间和，顾名思义，是∑_jw_jC_j。这两个问题都是NP难解的，并且前者是强NP难解的。在批调度的各种目标函数中，极小化加权完工时间和是最难的之一，对于这两个问题，我们均首次给出了多项式时间近似方案，有一点奇怪，在我们的算法中，那些处理批调度问题的技巧用的并不多，反而更多地依赖于研究经典调度问题(B=1)所发展起来的技巧。
第四章主要研究极小化最大延迟的有界批机器并行调度问题。每个工件j最好能在它的交货期d_j之前完工，最大延迟定义为max_j{C_j-d_j)。这个问题是强NP难解的。我们给出了第一个多项式时间近似方案，所用技巧经过简单修改之后，就得到(NP难解的)极小化最大延迟的并行机无界批调度问题的第一个多项式时间近似方案。当所有的d_j为0时，最大延迟就是最大完工时间，max_jC_j。因此我们也得到了求解极小化最大完工时间的有界批机器和无界批机器并行调度问题的多项式时间近似方案。
第五章研究了工件具有不同尺寸的单机批调度问题，目标函数是极小化最大完工时间，每个工件j有一个尺寸s_j∈(0，1]，批机器可以将若干个工件作为一批同时进行加工，只要这些工件的尺寸之和不超过1，工件尺寸不同的调度问题是批调度问题的一般形式。显然，此时我们不必考虑无界模式，最大完工时间，正如上面所定义的，是调度中所有工件的完工时间的最大者，对于这个问题，我们给出了(2+ε)-近似算法，ε是任意小的正数，算法的运行时间是O(n log n)+f(1／ε)，隐藏在O(n log n)中的常系数很小并且与ε无关，当所有工件同时到达并且加工时间相同时，这一问题就是经典的一维装箱问题。一维装箱问题是强NP难解的，近似比小于3／2的近似算法很可能不存在。
除了批调度问题，我们还研究通讯网络中出现的优化问题，通讯网络在我们的社会经济生活中日显其重要性，因此关于网络设计与有效运营的优化问题受到了学界的普遍关注，除去大量的实际应用之外，网络问题也有很多有趣的方法论特性。我们集中研究环网络，作为一种流行的通讯网络，环网络引起了很多人的兴趣。
在第六章，我们考虑环网络中的呼叫接纳控制问题，给定一个环(无向或有向)和一组通讯请求，每个请求用一对顶点(无序或有序)表示，并且有一个利润。要在无向环中实现一个呼叫，需在环中指定该请求所对应的两个顶点之间的一条路，要在有向环中实现一个呼叫，需在环中指定该请求的源节点到目的节点的一条路，环(无向或有向)网络呼叫接纳控制问题的目标是确定最大利润的呼叫子集，在环中实现该子集中的每一个呼叫，使得经过每一边(无向或有向)的呼叫的数目不超过该边的容量，对于无向和有向环网络呼叫接纳控制问题，我们均首次给出了多项式时间近似方案。
在第七章，我们研究多纤WDM网络中的利润极大化问题，要在多纤WDM网络中实现一组传输请求，我们要为其中每一个请求安排一条路并分配一个波长，使得任一链路上任一波长的使用次数不超过该链路上的光纤数，给定一个波长数目有限的多纤WDM网络和一组传输请求，利润极大化问题的目标是要确定利润最大的并且可以在网络中实现的那一部分传输请求，第六章所研究的呼叫接纳控制问题，是这一问题只有一个波长时的特例。对于链网，我们给出了多项式时间精确算法。环网中的这一问题是NP难解的，即使所有传输请求的利润均为1时也是如此。我们给出了两个算法，近似比分别为2和1.582+ε，ε是任意小的正数，对于环上各边光纤数目相同的均匀模式，给出了1.582-近似算法，这些结果也适用于有向链网与环网。注意在将多纤环网中的2-近似算法推广到有向多纤环网时，要求某一链路上的两条有向边分别为顺时针和逆时针方向上容量最小的有向边。
最后，在第八章我们引入了圈中t-区间的k-染色问题。这一问题推广了WDM环网络中几个熟知的优化问题，圈代表环网络，颜色代表波长，t-区间代表客户请求。一个t-区间，由圈上至多(t≥1)个区间构成，每个区间的两个端点都是圈上的顶点。要实现一个客户请求，需选择它所对应的t-区间中的一个区间并为其安排一种颜色，任意两个请求在实现时，所选定的两个区间如果在圈上有公共边，则不能得到同一种颜色，否则会引起波长冲突。给定一个圈、k种颜色和若干个请求(t-区间)，问题的目标是实现最大数目的请求。我们给出了这一问题的一个3.042-近似算法。顺便也得到了链网中t-区间的k-染色问题的一个2.542-近似算法。
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.
当多项式时间精确算法很可能不存在时(所谓的NP难解问题)，我们转而设计有效的近似算法以得到次优解，对于极小化问题，算法的近似比(性能比)定义为算法给出的解的目标值与最优值之间的最坏情形比，对于极大化问题，算法的近似比(性能比)定义为最优值与算法给出的解的目标值之间的最坏情形比，近似比为ρ的算法称为ρ-近似算法。通常用近似比来衡量算法的性能，近似比越小，算法越好，
一族算法{A_ε}称为一个多项式时间近似方案(PTAS)，如果对于每一个给定的正数ε，算法A_ε是一个运行于输入规模的多项式时间之内的(1+ε)-近似算法。注意到ε是给定的，因此算法的运行时间可以以任意方式依赖于1／ε。如果运行时间也是1／ε的多项式，我们就得到了全多项式时间近似方案(FPTAS)。对于NP难解问题和所谓的强NP难解问题来说，全多项式时间近似方案和多项式时间近似方案分别是我们目前所能得到的最好结果。
本文研究批调度和网络中的若干确定性优化问题，给出了有效的组合算法。确定性是指问题实例的所有参数均事先已知，我们研究的问题大多是NP难解的，所给出的算法大多是多项式时间近似方案，其余的是精确算法或常数近似比算法。下面简略地描述所研究的问题，并给出主要结果和创新点。
论文第一章介绍了研究的缘起和背景，第二章至第五章是第一部分，给出了若干批调度问题的组合算法；第六章至第八章是第二部分，给出了若干网络问题的组合算法。
一个典型的调度问题包含n个工件和m台机器，在满足一定约束条件下，要将工件安排在机器上进行加工。目标是找到一个最优的安排，最优性由依赖于问题的目标函数所定义。本文研究分批调度问题，每台机器可以同时加工若干个工件，这些工件构成一个批次，这样的机器称为批机器。将工件分批加工是为了提高效率，分批加工比一个一个加工更快或成本更低。
批调度问题有多种模式，本文研究如下的煅烧模式。给定n个工件和m台并行同型批机器，每个工件有一个加工时间，描述了在任意一台机器上加工该工件所需要的最短时间。每个工件还有一个释放时间，在该时间之前不能开始加工这个工件，一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者。一个批次的完工时间等于它的开工时间加上它的加工时间，同一批次中的所有工件有相同的开工时间，也有相同的完工时间，即该批次的完工时间。一个批次从开始加工到完工，不允许向内添加工件或向外移除工件。每个批次的加工都是连续进行的，即：从开工到完工，没有其他批次可以在同一台机器上加工，煅烧模式起源于大规模集成电路生产过程中的煅烧操作调度问题。
煅烧模式分为两类，有界模式：每个批次最多可容纳的工件数目(批容量)B小于工件的总数目n，B表示任一台机器能同时加工的工件的最大数目。无界模式：每个批次可容纳的工件数目没有限制，即B≥n，无界模式的一个例子：在干燥炉中硬化一些化合物，干燥炉足够大因此批容量没有限制。注意有界模式中B=1的情形，就是经典的调度问题(每台机器在任一时间至多加工一个工件)，因此，有界模式的批调度问题，难度不低于经典的调度问题。
集中研究工件释放时间不相同的调度问题，这比所有工件同时到达的问题要难得多，研究三种调度目标：极小化加权完工时间和、极小化最大延迟、极小化最大完工时间，记工件j在一个调度中的完工时间为C_j。
在第二章和第三章，我们研究极小化加权完工时间和的有界批机器和无界批机器并行调度问题，每个工件j有正权w_j。加权完工时间和，顾名思义，是∑_jw_jC_j。这两个问题都是NP难解的，并且前者是强NP难解的。在批调度的各种目标函数中，极小化加权完工时间和是最难的之一，对于这两个问题，我们均首次给出了多项式时间近似方案，有一点奇怪，在我们的算法中，那些处理批调度问题的技巧用的并不多，反而更多地依赖于研究经典调度问题(B=1)所发展起来的技巧。
第四章主要研究极小化最大延迟的有界批机器并行调度问题。每个工件j最好能在它的交货期d_j之前完工，最大延迟定义为max_j{C_j-d_j)。这个问题是强NP难解的。我们给出了第一个多项式时间近似方案，所用技巧经过简单修改之后，就得到(NP难解的)极小化最大延迟的并行机无界批调度问题的第一个多项式时间近似方案。当所有的d_j为0时，最大延迟就是最大完工时间，max_jC_j。因此我们也得到了求解极小化最大完工时间的有界批机器和无界批机器并行调度问题的多项式时间近似方案。
第五章研究了工件具有不同尺寸的单机批调度问题，目标函数是极小化最大完工时间，每个工件j有一个尺寸s_j∈(0，1]，批机器可以将若干个工件作为一批同时进行加工，只要这些工件的尺寸之和不超过1，工件尺寸不同的调度问题是批调度问题的一般形式。显然，此时我们不必考虑无界模式，最大完工时间，正如上面所定义的，是调度中所有工件的完工时间的最大者，对于这个问题，我们给出了(2+ε)-近似算法，ε是任意小的正数，算法的运行时间是O(n log n)+f(1／ε)，隐藏在O(n log n)中的常系数很小并且与ε无关，当所有工件同时到达并且加工时间相同时，这一问题就是经典的一维装箱问题。一维装箱问题是强NP难解的，近似比小于3／2的近似算法很可能不存在。
除了批调度问题，我们还研究通讯网络中出现的优化问题，通讯网络在我们的社会经济生活中日显其重要性，因此关于网络设计与有效运营的优化问题受到了学界的普遍关注，除去大量的实际应用之外，网络问题也有很多有趣的方法论特性。我们集中研究环网络，作为一种流行的通讯网络，环网络引起了很多人的兴趣。
在第六章，我们考虑环网络中的呼叫接纳控制问题，给定一个环(无向或有向)和一组通讯请求，每个请求用一对顶点(无序或有序)表示，并且有一个利润。要在无向环中实现一个呼叫，需在环中指定该请求所对应的两个顶点之间的一条路，要在有向环中实现一个呼叫，需在环中指定该请求的源节点到目的节点的一条路，环(无向或有向)网络呼叫接纳控制问题的目标是确定最大利润的呼叫子集，在环中实现该子集中的每一个呼叫，使得经过每一边(无向或有向)的呼叫的数目不超过该边的容量，对于无向和有向环网络呼叫接纳控制问题，我们均首次给出了多项式时间近似方案。
在第七章，我们研究多纤WDM网络中的利润极大化问题，要在多纤WDM网络中实现一组传输请求，我们要为其中每一个请求安排一条路并分配一个波长，使得任一链路上任一波长的使用次数不超过该链路上的光纤数，给定一个波长数目有限的多纤WDM网络和一组传输请求，利润极大化问题的目标是要确定利润最大的并且可以在网络中实现的那一部分传输请求，第六章所研究的呼叫接纳控制问题，是这一问题只有一个波长时的特例。对于链网，我们给出了多项式时间精确算法。环网中的这一问题是NP难解的，即使所有传输请求的利润均为1时也是如此。我们给出了两个算法，近似比分别为2和1.582+ε，ε是任意小的正数，对于环上各边光纤数目相同的均匀模式，给出了1.582-近似算法，这些结果也适用于有向链网与环网。注意在将多纤环网中的2-近似算法推广到有向多纤环网时，要求某一链路上的两条有向边分别为顺时针和逆时针方向上容量最小的有向边。
最后，在第八章我们引入了圈中t-区间的k-染色问题。这一问题推广了WDM环网络中几个熟知的优化问题，圈代表环网络，颜色代表波长，t-区间代表客户请求。一个t-区间，由圈上至多(t≥1)个区间构成，每个区间的两个端点都是圈上的顶点。要实现一个客户请求，需选择它所对应的t-区间中的一个区间并为其安排一种颜色，任意两个请求在实现时，所选定的两个区间如果在圈上有公共边，则不能得到同一种颜色，否则会引起波长冲突。给定一个圈、k种颜色和若干个请求(t-区间)，问题的目标是实现最大数目的请求。我们给出了这一问题的一个3.042-近似算法。顺便也得到了链网中t-区间的k-染色问题的一个2.542-近似算法。
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.
引文
[1] U. Adamy, C. Arabuehl, R. S. Anand, T. Erlebach. Call control in rings. Lecture Notes in Computer Science 2380: Proceedings of the 29th International Colloquium on Automata, Languages and Programming. Heidelberg: Springer-Verlag, 2002, 788-799.
[2] F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. New York, USA, 1999, 32-43.
[3] J. H. Ahmadi, R. H. Ahmadi, S. Dasu, C. S. Tang. Batching and scheduling jobs on batch and discrete processors. Operations Research, 1992, 40(4): 750-763.
[4] S. Albers, P. Brucker. The complexity of one-machine batching problems. Discrete Applied Mathematics, 1993, 47(2): 87-107.
[5] R. S. Anand, T. Erlebach, A. Hall, S. Stefanakos. Routing and call control algorithms for ring networks. Lecture Notes in Computer Science 2748: Proceedings of the 8th International Workshop on Algorithms and Data Structures. Heidelberg: Springer-Verlag, 2003, 186-197.
[6] V. Anand, T. Katarki, C. Qiao. Profitable connection assignment in all optical WDM networks. IEEE/ACM Workshop on Optical Networks, Dallas, 2000.
[7] V. Anand, T. Katarki, C. Qiao. Profitable connection assignment for incremental traffic in all-optical WDM networks. Proceedings of the Academia/Industry Working Conference on Research Challenges. Washington: IEEE Computer Society, 2000, 355-360.
[8] B. Awerbuch, Y. Azar, A. Fiat, S. Leonardi, A. Rosen. On-line competitive algorithms for call admission in optical networks. Lecture Notes in Computer Science 1136: Proceedings of the 4th Annual European Symposium on Algorithms. Heidelberg: Springer-Berlin, 1996, 431-444.
[9] J. A. Bondy and U. S. R. Murty. Graph theory with applications. Macmillan Press, 1976.
[10] B. Beauquier, J. C. Bermond, L. Gargano, P. Hell, S. Perennes, U. Vaccaro. Graph problems arising from wavelength-routing in all-optical networks. Proceedings of the 2nd Workshop on Optics and Computer Science. Geneva, Switzerland: IEEE Press, 1997.
[11] P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. N. Potts, T. Tautenhahn, S. L. vande Velde, Scheduling a batching machine. Journal of Scheduling, 1998, 1(1): 31-54.
[12] M. Cai, X. Deng, H. Feng, G. Li, G. Liu. A PTAS for minimizing total completion time of bounded batch scheduling. Lecture Notes in Computer Science 2337: Proceedings of the 9th International Integer Programming and Combinatorial Optimization. Cambridge: Spring-Verlag, 2002, 304-314.
[13] M. C. Carlisle, E. L. Lloyd. On the k-coloring of intervals. Discrete Applied Mathematics, 1995, 59: 225-235.
[14] V. Chandru, C. Y. Lee, R. Uzsoy. Minimizing total completion time on batch processing machines. International Journal of Production Research, 1993, 31(9): 2097-2121.
[15] C. Chekuri, S. Khanna. Approximation algorithms for minimizing average weighted completion time. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton, FL, USA, 2004.
[16] B. Chen, X. Deng, W. Zang, On-line scheduling a batch processing system to minimize total weighted job completion time. Journal of Combinatorial Optimization, 2004, 8(1): 85-95.
[17] T. C. E. Cheng, Z. Liu, W. Yu. Scheduling jobs with release dates and deadlines on a batch processing machine. IIE Transactions, 2001, 33: 685-690.
[18] E. G. Coffman, M. R. Garey, D. S. Johnson. Approximation algorithms for bin packing: a survey. Approximation Algorithms for NP-hardProblems, PWS, Boston, 1996, 46-93.
[19] X. Deng, H. Feng, G. J. Li, B. Y. Shi. A PTAS for semiconductor burn-in scheduling. Journal of Combinatorial Optiraization, 2005, 9(1): 5-17.
[20] X. Deng, H. Feng, P. Zhang, H. Zhao. A polynomial time approximation scheme for minimizing total completion time of unbounded batch scheduling. Lecture Notes in Computer Science 2223: proceedings of International Symposium on Symbolic and Algebraic Computation. New Zealand: Springer-Verlng, 2001, 26-35.
[21] X. Deng, C. K. Poon, Y. Zhang. Approximation algorithms in batch processing. Lecture Notes in Computer Science 1741: Proceedings of the Eighth Annual International Symposium on Algorithms and Computation. Chennal: Springer-verlag, 1999, 153-162.
[22] X. Deng, Y. Zhang. Minimizing mean response time in batch processing system. Lecture Notes in Computer Science 1627: Proceedings of the 5th Annual International Conference on Computing and Combinatorics. Tokyo: Springer-Verlng, 1999, 231-240.
[23] T. Erlebach, K. Jansen. Maximizing the number of connections in optical tree networks. Lecture Notes in Computer Science 1533: Proceedings of the 9th Annual International Symposium on Algorithms and Computation. Heidelberg: Springer-Berlin, 1998, 179-188.
[24] T. Erlebach, A. Pagourtzis, K. Potika, S. Stefanakos. Resource allocation problems in multifiber WDM tree networks. Lecture Notes in Computer Science 2880: Proceedings of the 29th Workshop on Graph Theoretic Concepts in Computer Science. Heidelberg: Springer-Verlag, 2003, 218-229.
[25] M L Fredman, R E Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 1987, 34(3): 596-615.
[26] M. R. Garey, D. S. Johnson. Computers and Intractability, a Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.
[27] N. Garg, V. Vazirani, M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 1997, 18(1): 3-20.
[28] L. Gargano, U. Vaccaro. Routing in all-optical networks: Algorithmic and graph-theoretic problems. I. Althofer, N. Cai, G. Dueck, L. Khachatrian, M. Pinsker, A. Sarkozy, I. Wegener, Z. Zhang, eds. Numbers, Information and Complexity. Amsterdam: Kluwer Academic Publishers, 2000, 555-578.
[29] R. L. Graham. Rounds for certain multiprocessor anomalies. Bell System Technical Journal, 1966, 45: 1563-1581.
[30] R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling. Annals of Discrete Mathematics, 1979, 5: 287-326.
[31] P E Green. Fiber Optic Networks. Englewood Cliffs, NJ: Prentice-Hall, 1993.
[32] L. A. Hall, D. B. Shmoys. Approximation schemes for constrained scheduling problems. Proceedings of the 30th Annual Symposium on Foundations of Computer Science, North Carolina, USA, 1989, 134-139.
[33] D. Hochbaum, D. Landy. Scheduling semiconductor burn-in operations to minimize total flowtime. Operations Research, 1997, 45(6): 874-885.
[34] C. Huitema. Routing in the Internet. Englewood Cliffs, New Jersey: Prentice-Hall, 2000.
[35] Y. Ikura, M. Gimple. Scheduling algorithms for a single batch processing machine. Operations Research Letters, 1986, 5: 61-65.
[36] J. R. Jackson. Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, UCLA, 1955.
[37] C. Kaklamanis, M. Mihail, S. Rao. Efficient access to optical bandwidth. Proceedings of the 36th Annual ACM Symposium on Foundations of Computer Science. IEEE Computer Society, 1995, 548-557.
[38] L. G. Khachiyan. A polynomial algorithm in linear programming. (in Russian), Doldady Akedamii Nauk SSSR, 1979, 244: 1093-1096.
[39] H. Kise, T. Ibaraki, H. Mine. Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times. Journal of the Operations Research Society of Japan, 1979, 22: 205-224.
[40] M. W. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 1988, 36: 490-509.
[41] E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, USA, 1976.
[42] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys. Sequencing and scheduling: algorithms and complexity. S. C. Graves, A. H. G. Rinnooy Kan, P. H. Zipkin, Eds., Handbooks in Operations Research and Management Science, Vol. 4, Logistics of Production and Inventory, North-Holland, Amsterdam, 1993, 445-522.
[43] C. Y. Lee, R. Uzsoy. Minimizing makespan on a single batch processing machine with dynamic job arrivals. Technical Report, Department of Industrial and System Engineering, University of Florida, January 1996.
[44] C. Y. Lee, R. Uzsoy, L. A. Martin Vega. Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 1992, 40(4): 764-775.
[45] J. K. Lenstra, A. H. G. Rinnooy Kan, P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1977, 1: 343-362.
[46] J. K. Lenstra, D. B. Shmoys. Computing near-optimal schedules, Scheduling Theory and its Application. Wiley, New York, 1995.
[47] C. L. Li, C. Y. Lee. Scheduling with agreeable release times and due dates on a batch processing machine. European Journal of Operational Research 1997, 96: 564-569.
[48] J. P. Li, K. Li, K. C. K. Law, H. Zhao. On packing and coloring hyperedges in a cycle. Lecture Notes in Computer Science 3595: Proceedings of the 11th International Computing and Combinatorics Conference. Heidelberg: Springer-Verlag, 2005, 220-229.
[49] J. P. Li, K. Li, L. S. Wang, H Zhao. Maximizing profits of routing in WDM networks. Journal of Combinatorial Optimization, 2005, 10: 99-111.
[50] S. G. Li, G. J. Li, H. Zhao. A linear time approximation scheme for minimizing total weighted completion time of unbounded batch scheduling. OR Transactions, 2004, 8(4): 27-32.
[51] S. Micali, V. Vazirani. An O(v~(1/2)E) algorithm for maximum matching in general graphs. Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. California: IEEE Computer Society Press, 1980, 17-27.
[52] B. Mukherjee. Optical Communication Networks. McGraw-Hill, New York, 1997.
[53] C. Nomikos, A. Pagourtzis, S. Zachos. Satisfying a maximum number of pre-routed requests in all-optical rings. Computer Networks, 2003, 42(1): 55-63.
[54] C. Nomikos, A. Pagourtzis, S. Zachos. Minimizing request blocking in all-optical rings. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies. San Francisco: IEEE Press, 2003.
[55] C. Nomikos, A. Pagourtzis, S. Zachos. Routing and path multicoloring. Information Processing Letters, 2001, 80: 249-256.
[56] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, MA, 1994.
[57] C. H. Papadimitriou, K. Steiglitz. Combinatorial optimization: algorithms and complexity. New Jersey: Prentice-Hall, 1982.
[58] C. K. Poon, W. Yu, On minimizing total completion time in batch machine scheduling. International Journal of Foundations of Computer Science, 2004, 15(4): 593-607.
[59] K. Potika. Maximizing the number of connections in multifiber WDM chain, ring and star networks. Lecture Notes in Computer Science 3462: Proceedings of the Networking 2005. Heidelberg: Springer-Berlin, 2005, 1465-1470.
[60] C. H. Potts, M. Y. Kovalyov. Scheduling with batching: a review. European Journal of Operational Research, 2000, 120(2): 228-249.
[61] P. Raghavan, E. Upfal. Efficient routing in all-optical networks. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, New York, 1994, 134-143.
[62] A Schrijver. Combinatorial optimization: polyhedra and efficiency. Heidelberg: Springer, 2003.
[63] A. Schrijver, P. Seymour, P. Wiulder. The ring loading problem. SIAM Journal on Discrete Mathematics, 1998, 11(1): 1-14.
[64] W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 1956, 3: 59-66.
[65] F. C. R. Spieksma. On the approximability of an interval scheduling problem. Journal of Scheduling, 1999, 2: 215-227.
[66] R E Tarjan. Data Structures and Network Algorithms. Philadelphia: SIAM, 1983.
[67] R. Uzsoy. A single batch processing machine with non-identical job sizes. International Journal of Production Research, 1994, 32: 1615-1635.
[68] P. J. Wan, L. Liu. Maximal throughput in wavelength-routed optical networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1998, 46: 15-26.
[69] C. S. Wang, R. Uzsoy. A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers and Operations Research, 2002, 29: 1621-1640.
[70] S. Webster, K. R. Baker. Scheduling groups of jobs on a single machine. Operations Research, 1995, 43(4): 692-703.
[71] G. Wilfong, P. Winkler. Ring routing and wavelength translation. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM Press, 1998, 333-341.
[72] G. Zhang, X. Cai, C. Y. Lee, C. K. Wong. Minimizing makespan on a single batch processing machine with non-identical job sizes. Naval Research Logistics, 2001, 48: 226-240.
[2] F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. New York, USA, 1999, 32-43.
[3] J. H. Ahmadi, R. H. Ahmadi, S. Dasu, C. S. Tang. Batching and scheduling jobs on batch and discrete processors. Operations Research, 1992, 40(4): 750-763.
[4] S. Albers, P. Brucker. The complexity of one-machine batching problems. Discrete Applied Mathematics, 1993, 47(2): 87-107.
[5] R. S. Anand, T. Erlebach, A. Hall, S. Stefanakos. Routing and call control algorithms for ring networks. Lecture Notes in Computer Science 2748: Proceedings of the 8th International Workshop on Algorithms and Data Structures. Heidelberg: Springer-Verlag, 2003, 186-197.
[6] V. Anand, T. Katarki, C. Qiao. Profitable connection assignment in all optical WDM networks. IEEE/ACM Workshop on Optical Networks, Dallas, 2000.
[7] V. Anand, T. Katarki, C. Qiao. Profitable connection assignment for incremental traffic in all-optical WDM networks. Proceedings of the Academia/Industry Working Conference on Research Challenges. Washington: IEEE Computer Society, 2000, 355-360.
[8] B. Awerbuch, Y. Azar, A. Fiat, S. Leonardi, A. Rosen. On-line competitive algorithms for call admission in optical networks. Lecture Notes in Computer Science 1136: Proceedings of the 4th Annual European Symposium on Algorithms. Heidelberg: Springer-Berlin, 1996, 431-444.
[9] J. A. Bondy and U. S. R. Murty. Graph theory with applications. Macmillan Press, 1976.
[10] B. Beauquier, J. C. Bermond, L. Gargano, P. Hell, S. Perennes, U. Vaccaro. Graph problems arising from wavelength-routing in all-optical networks. Proceedings of the 2nd Workshop on Optics and Computer Science. Geneva, Switzerland: IEEE Press, 1997.
[11] P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. N. Potts, T. Tautenhahn, S. L. vande Velde, Scheduling a batching machine. Journal of Scheduling, 1998, 1(1): 31-54.
[12] M. Cai, X. Deng, H. Feng, G. Li, G. Liu. A PTAS for minimizing total completion time of bounded batch scheduling. Lecture Notes in Computer Science 2337: Proceedings of the 9th International Integer Programming and Combinatorial Optimization. Cambridge: Spring-Verlag, 2002, 304-314.
[13] M. C. Carlisle, E. L. Lloyd. On the k-coloring of intervals. Discrete Applied Mathematics, 1995, 59: 225-235.
[14] V. Chandru, C. Y. Lee, R. Uzsoy. Minimizing total completion time on batch processing machines. International Journal of Production Research, 1993, 31(9): 2097-2121.
[15] C. Chekuri, S. Khanna. Approximation algorithms for minimizing average weighted completion time. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton, FL, USA, 2004.
[16] B. Chen, X. Deng, W. Zang, On-line scheduling a batch processing system to minimize total weighted job completion time. Journal of Combinatorial Optimization, 2004, 8(1): 85-95.
[17] T. C. E. Cheng, Z. Liu, W. Yu. Scheduling jobs with release dates and deadlines on a batch processing machine. IIE Transactions, 2001, 33: 685-690.
[18] E. G. Coffman, M. R. Garey, D. S. Johnson. Approximation algorithms for bin packing: a survey. Approximation Algorithms for NP-hardProblems, PWS, Boston, 1996, 46-93.
[19] X. Deng, H. Feng, G. J. Li, B. Y. Shi. A PTAS for semiconductor burn-in scheduling. Journal of Combinatorial Optiraization, 2005, 9(1): 5-17.
[20] X. Deng, H. Feng, P. Zhang, H. Zhao. A polynomial time approximation scheme for minimizing total completion time of unbounded batch scheduling. Lecture Notes in Computer Science 2223: proceedings of International Symposium on Symbolic and Algebraic Computation. New Zealand: Springer-Verlng, 2001, 26-35.
[21] X. Deng, C. K. Poon, Y. Zhang. Approximation algorithms in batch processing. Lecture Notes in Computer Science 1741: Proceedings of the Eighth Annual International Symposium on Algorithms and Computation. Chennal: Springer-verlag, 1999, 153-162.
[22] X. Deng, Y. Zhang. Minimizing mean response time in batch processing system. Lecture Notes in Computer Science 1627: Proceedings of the 5th Annual International Conference on Computing and Combinatorics. Tokyo: Springer-Verlng, 1999, 231-240.
[23] T. Erlebach, K. Jansen. Maximizing the number of connections in optical tree networks. Lecture Notes in Computer Science 1533: Proceedings of the 9th Annual International Symposium on Algorithms and Computation. Heidelberg: Springer-Berlin, 1998, 179-188.
[24] T. Erlebach, A. Pagourtzis, K. Potika, S. Stefanakos. Resource allocation problems in multifiber WDM tree networks. Lecture Notes in Computer Science 2880: Proceedings of the 29th Workshop on Graph Theoretic Concepts in Computer Science. Heidelberg: Springer-Verlag, 2003, 218-229.
[25] M L Fredman, R E Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 1987, 34(3): 596-615.
[26] M. R. Garey, D. S. Johnson. Computers and Intractability, a Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.
[27] N. Garg, V. Vazirani, M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 1997, 18(1): 3-20.
[28] L. Gargano, U. Vaccaro. Routing in all-optical networks: Algorithmic and graph-theoretic problems. I. Althofer, N. Cai, G. Dueck, L. Khachatrian, M. Pinsker, A. Sarkozy, I. Wegener, Z. Zhang, eds. Numbers, Information and Complexity. Amsterdam: Kluwer Academic Publishers, 2000, 555-578.
[29] R. L. Graham. Rounds for certain multiprocessor anomalies. Bell System Technical Journal, 1966, 45: 1563-1581.
[30] R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling. Annals of Discrete Mathematics, 1979, 5: 287-326.
[31] P E Green. Fiber Optic Networks. Englewood Cliffs, NJ: Prentice-Hall, 1993.
[32] L. A. Hall, D. B. Shmoys. Approximation schemes for constrained scheduling problems. Proceedings of the 30th Annual Symposium on Foundations of Computer Science, North Carolina, USA, 1989, 134-139.
[33] D. Hochbaum, D. Landy. Scheduling semiconductor burn-in operations to minimize total flowtime. Operations Research, 1997, 45(6): 874-885.
[34] C. Huitema. Routing in the Internet. Englewood Cliffs, New Jersey: Prentice-Hall, 2000.
[35] Y. Ikura, M. Gimple. Scheduling algorithms for a single batch processing machine. Operations Research Letters, 1986, 5: 61-65.
[36] J. R. Jackson. Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, UCLA, 1955.
[37] C. Kaklamanis, M. Mihail, S. Rao. Efficient access to optical bandwidth. Proceedings of the 36th Annual ACM Symposium on Foundations of Computer Science. IEEE Computer Society, 1995, 548-557.
[38] L. G. Khachiyan. A polynomial algorithm in linear programming. (in Russian), Doldady Akedamii Nauk SSSR, 1979, 244: 1093-1096.
[39] H. Kise, T. Ibaraki, H. Mine. Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times. Journal of the Operations Research Society of Japan, 1979, 22: 205-224.
[40] M. W. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 1988, 36: 490-509.
[41] E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, USA, 1976.
[42] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys. Sequencing and scheduling: algorithms and complexity. S. C. Graves, A. H. G. Rinnooy Kan, P. H. Zipkin, Eds., Handbooks in Operations Research and Management Science, Vol. 4, Logistics of Production and Inventory, North-Holland, Amsterdam, 1993, 445-522.
[43] C. Y. Lee, R. Uzsoy. Minimizing makespan on a single batch processing machine with dynamic job arrivals. Technical Report, Department of Industrial and System Engineering, University of Florida, January 1996.
[44] C. Y. Lee, R. Uzsoy, L. A. Martin Vega. Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 1992, 40(4): 764-775.
[45] J. K. Lenstra, A. H. G. Rinnooy Kan, P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1977, 1: 343-362.
[46] J. K. Lenstra, D. B. Shmoys. Computing near-optimal schedules, Scheduling Theory and its Application. Wiley, New York, 1995.
[47] C. L. Li, C. Y. Lee. Scheduling with agreeable release times and due dates on a batch processing machine. European Journal of Operational Research 1997, 96: 564-569.
[48] J. P. Li, K. Li, K. C. K. Law, H. Zhao. On packing and coloring hyperedges in a cycle. Lecture Notes in Computer Science 3595: Proceedings of the 11th International Computing and Combinatorics Conference. Heidelberg: Springer-Verlag, 2005, 220-229.
[49] J. P. Li, K. Li, L. S. Wang, H Zhao. Maximizing profits of routing in WDM networks. Journal of Combinatorial Optimization, 2005, 10: 99-111.
[50] S. G. Li, G. J. Li, H. Zhao. A linear time approximation scheme for minimizing total weighted completion time of unbounded batch scheduling. OR Transactions, 2004, 8(4): 27-32.
[51] S. Micali, V. Vazirani. An O(v~(1/2)E) algorithm for maximum matching in general graphs. Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. California: IEEE Computer Society Press, 1980, 17-27.
[52] B. Mukherjee. Optical Communication Networks. McGraw-Hill, New York, 1997.
[53] C. Nomikos, A. Pagourtzis, S. Zachos. Satisfying a maximum number of pre-routed requests in all-optical rings. Computer Networks, 2003, 42(1): 55-63.
[54] C. Nomikos, A. Pagourtzis, S. Zachos. Minimizing request blocking in all-optical rings. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies. San Francisco: IEEE Press, 2003.
[55] C. Nomikos, A. Pagourtzis, S. Zachos. Routing and path multicoloring. Information Processing Letters, 2001, 80: 249-256.
[56] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, MA, 1994.
[57] C. H. Papadimitriou, K. Steiglitz. Combinatorial optimization: algorithms and complexity. New Jersey: Prentice-Hall, 1982.
[58] C. K. Poon, W. Yu, On minimizing total completion time in batch machine scheduling. International Journal of Foundations of Computer Science, 2004, 15(4): 593-607.
[59] K. Potika. Maximizing the number of connections in multifiber WDM chain, ring and star networks. Lecture Notes in Computer Science 3462: Proceedings of the Networking 2005. Heidelberg: Springer-Berlin, 2005, 1465-1470.
[60] C. H. Potts, M. Y. Kovalyov. Scheduling with batching: a review. European Journal of Operational Research, 2000, 120(2): 228-249.
[61] P. Raghavan, E. Upfal. Efficient routing in all-optical networks. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, New York, 1994, 134-143.
[62] A Schrijver. Combinatorial optimization: polyhedra and efficiency. Heidelberg: Springer, 2003.
[63] A. Schrijver, P. Seymour, P. Wiulder. The ring loading problem. SIAM Journal on Discrete Mathematics, 1998, 11(1): 1-14.
[64] W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 1956, 3: 59-66.
[65] F. C. R. Spieksma. On the approximability of an interval scheduling problem. Journal of Scheduling, 1999, 2: 215-227.
[66] R E Tarjan. Data Structures and Network Algorithms. Philadelphia: SIAM, 1983.
[67] R. Uzsoy. A single batch processing machine with non-identical job sizes. International Journal of Production Research, 1994, 32: 1615-1635.
[68] P. J. Wan, L. Liu. Maximal throughput in wavelength-routed optical networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1998, 46: 15-26.
[69] C. S. Wang, R. Uzsoy. A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers and Operations Research, 2002, 29: 1621-1640.
[70] S. Webster, K. R. Baker. Scheduling groups of jobs on a single machine. Operations Research, 1995, 43(4): 692-703.
[71] G. Wilfong, P. Winkler. Ring routing and wavelength translation. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM Press, 1998, 333-341.
[72] G. Zhang, X. Cai, C. Y. Lee, C. K. Wong. Minimizing makespan on a single batch processing machine with non-identical job sizes. Naval Research Logistics, 2001, 48: 226-240.