优化是根据现状采取行动以获得最好(或最优)的结果．组合最优化研究的是可行解数目有限的离散优化问题．在复杂性理论的框架下，我们希望能在输入规模的多项式时间之内找到最优解．运行在多项式时间之内的算法称为有效算法．输出最优解的有效算法称为精确(或最优)算法． 当多项式时间精确算法很可能不存在时(所谓的NP难解问题)，我们转而设计有效的近似算法以得到次优解．对于极小化问题，算法的近似比(性能比)定义为算法给出的解的目标值与最优值之间的最坏情形比．对于极大化问题，算法的近似比(性能比)定义为最优值与算法给出的解的目标值之间的最坏情形比．近似比为P的算法称为p近似算法．通常用近似比来衡量算法的性能；近似比越小，算法越好． 一族算法{A￡)称为一个多项式时间近似方案(PTAS)，如果对于每一个给定的正数e，算法A是一个运行于输入规模的多项式时间之内的(1+E)一近似算法．注意到E是给定的，因此算法的运行时间可以以任意方式依赖于1／E．如果运行时间也是1／E的多项式，我们就得到了全多项式时间近似方案(FPTAS)．对于NP难解问题和所谓的强NP难解问题来说，全多项式时间近似方案和多项式时间近似方案分别是我们目前所能得到的最好结果． 本文研究批调度和网络中的若干确定性优化问题，给出了有效的组合算法．确定性是指问题实例的所有参数均事先已知．我们研究的问题大多是NP难解的，所给出的算法大多是多项式时间近似方案，其余的是精确算法或常数近似比算法．下面简略地描述所研究的问题，并给出主要结果和创新点． 论文第一章介绍了研究的缘起和背景．第二章至第五章是第一部分，给出了若干批调度问题的组合算法；第六章至第八章是第二部分，给出了若干网络问题的组合算法． 一个典型的调度问题包含n个工件和m台机器．在满足一定约束条件下，要将工件安排在机器上进行加工．目标是找到一个最优的安排．最优性由依赖于问题的目标函数所定义．本文研究分批调度问题．每台机器可以同时加工若干个工件，这些工件构成一个批次．这样的机器称为批机器．将工件分批加工是为了提高效率；分批加工比一个一个加工更快或成本更低． 批调度问题有多种模式．本文研究如下的煅烧模式．给定n个工件和m台并行同型批机器．每个工件有一个加工时间，描述了在任意一台机器上加工该工件所需要的最短时间．每个工件还有一个释放时间，在该时间之前不能开始加工这个工件．一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者．一个批次的完工时间等于它的开工时间加上它的加工时间．同一批次中的所有工件有相同的开工时间，也有相同的完工时间，即该批次的完工时间．一个批次从开始加工到完工。不允许向内添加工件或向外移除工件．每个批次的加工都是连续进行的，即；从开工到完工，没有其他批次可以在同一台机器上加工．煅烧模式起源于大规模集成电路生产过程中的煅烧操作调度问题． 煅烧模式分为两类．有界模式:每个批次最多可容纳的工件数目(批容量)B小于工件的总数目n，B表示任一台机器能同时加工的工件的最大数目．无界模式:每个批次可容纳的工件数目没有限制，即B≥n．无界模式的一个例子：在干燥炉中硬化一些化合物，干燥炉足够大因此批容量没有限制．注意有界模式中B=1的情形，就是经典的调度问题(每台机器在任一时间至多加工一个工件)．因此，有界模式的批调度问题，难度不低于经典的调度问题． 集中研究工件释放时间不相同的调度问题．这比所有工件同时到达的问题要难得多．研究三种调度目标；极小化加权完工时间和、极小化最大延迟、极小化最大完工时间．记工件J在一个调度中的完工时间为C<,j>． 在第二章和第三章，研究了极小化加权完工时间和的有界批机器和无界批机器并行调度问题．每个工件j有正权ω<,j>．加权完工时间和，顾名思义，是∑<,j>ω<,j>C<,j>．这两个问题都是NP难解的，并且前者是强NP难解的．在批调度的各种目标函数中，极小化加权完工时间和是最难的之一．对于这两个问题，我们均首次给出了多项式时间近似方案．有一点奇怪，在我们的算法中，那些处理批调度问题的技巧用的并不多，反而更多地依赖于研究经典调度问题(B=1)所发展起来的技巧． 第四章主要研究极小化最大延迟的有界批机器并行调度问题．每个工件j最好能在它的交货期dJ之前完工．最大延迟定义为max<,j>{c<,j>-d<,j>}．这个问题是强NP难解的．我们给出了第一个多项式时间近似方案．所用技巧经过简单修改之后，就得到(NP难解的)极小化最大延迟的并行机无界批调度问题的第一个多项式时间近似方案．当所有的d为0时，最大延迟就是最大完工时间，max<,j>C<,j>．因此我们也得到了求解极小化最大完工时间的有界批机器和无界批机器并行调度问题的多项式时间近似方案．第五章研究了工件具有不同尺寸的单机批调度问题，目标函数是极小化最大完工时间．每个工件j有一个尺寸s<,j> ∈(O，1]．批机器可以将若干个工件作为一批同时进行加工，只要这些工件的尺寸之和不超过1．工件尺寸不同的调度问题是批调度问题的一般形式．显然，此时我们不必考虑无界模式．最大完工时间，正如上面所定义的，是调度中所有工件的完工时间的最大者．对于这个问题，我们给出了(2+∈)一近似算法，∈是任意小的正数．算法的运行时间是O(n log n)+f(1/∈)，隐藏在o(n log n)中的常系数很小并且与∈无关．当所有工件同时到达并且加工时间相同时，这一问题就是经典的一维装箱问题．一维装箱问题是强NP难解的，近似比小于3/2的近似算法很可能不存在． 除了批调度问题，我们还研究通讯网络中出现的优化问题．通讯网络在我们的社会经济生活中日显其重要性，因此关于网络设计与有效运营的优化问题受到了学界的普遍关注．除去大量的实际应用之外，网络问题也有很多有趣的方法论特性．我们集中研究环网络．作为一种流行的通讯网络，环网络引起了很多人的兴趣． 在第六章，考虑环网络中的呼叫接纳控制问题．给定一个环(无向或有向)和一组通讯请求．每个请求用一对顶点(无序或有序)表示，并且有一个利润．要在无向环中实现一个呼叫，需在环中指定该请求所对应的两个顶点之间的一条路．要在有向环中实现一个呼叫，需在环中指定该请求的源节点到目的节点的一条路．环(无向或有向)网络呼叫接纳控制问题的目标是确定最大利润的呼叫子集，在环中实现该子集中的每一个呼叫，使得经过每一边(无向或有向)的呼叫的数目不超过该边的容量．对于无向和有向环网络呼叫接纳控制问题，我们均首次给出了多项式时间近似方案． 在第七章，研究了多纤WDM网络中的利润极大化问题．要在多纤WDM网络中实现一组传输请求，我们要为其中每一个请求安排一条路并分配一个波长，使得任一链路上任一波长的使用次数不超过该链路上的光纤数．给定一个波长数目有限的多纤WDM网络和一组传输请求，利润极大化问题的目标是要确定利润最大的并且可以在网络中实现的那一部分传输请求.第六章所研究的呼叫接纳控制问题，是这一问题只有一个波长时的特例.对于链网，我们给出了多项式时间精确算法.环网中的这一问题是NP难解的，即使所有传输请求的利润均为1时也是如此.我们给出了两个算法，近似比分别为2和1.582+∈，E是任意小的正数.对于环上各边光纤数目相同的均匀模式，给出了1.582-近似算法.这些结果也适用于有向链网与环网.注意在将多纤环网中的2-近似算法推广到有向多纤环网时，要求某一链路上的两条有向边分别为顺时针和逆时针方向上容量最小的有向边. 最后，在第八章我们引入了圈中t-区间的k-染色问题.这一问题推广了WDM环网络中几个熟知的优化问题.圈代表环网络，颜色代表波长，t-区间代表客户请求.一个t-区间，由圈上至多(t≥1)个区间构成，每个区间的两个端点都是圈上的顶点.要实现一个客户请求，需选择它所对应的t-区间中的一个区间并为其安排一种颜色.任意两个请求在实现时，所选定的两个区间如果在圈上有公共边，则不能得到同一种颜色，否则会引起波长冲突.给定一个圈、k-种颜色和若干个请求(t-区间)，问题的目标是实现最大数目的请求.我们给出了这一问题的一个3.042-近似算法.顺便也得到了链网中t-区间的k--染色问题的一个2.542-近似算法.