[01618314]电路与网络中优化问题的算法分析与设计

该课题是天津市高等学校科技发展基金项目，项目名称为“电路与网络中优化问题的算法分析与设计”。在很多新兴的科学技术领域中不断遇到大量的优化设计和科学计算问题，这些问题往往非常复杂，在实际操作中无法在很短时间内获得精确或最佳的设计方案。而这些问题经常困扰工程技术人员，使他们无法高效快速地开发设计出更好的产品。为了优化设计就必须在设计前进行科学的计算，分析出现的问题的复杂性以便设计高效的算法，进而可以优化设计，达到尽量避免设计缺陷、设计冗余、设计逻辑错误等。对其中产生的各种现实问题进行优化算法设计加以解决就迫在眉睫。课题组分阶段有序地开展三个问题的研究。第一个是集成半导体电路芯片制造工艺流程中对煅烧(Semi-conductorBurn-in)工序的分批排序(batchscheduling)问题研究。煅烧工序的一个最优目标就是最小化所有需要煅烧芯片的最大交付时间，以便能在规定时间完成所有芯片的工序任务。课题组发现芯片煅烧炉可以看成一个能同时加工多个工件的处理机，因为每个工件都有一个允许其加工的释放时间(releasedate)和一个完成加工后的额外交付时间(deliverytime)，所以所有工件需要先分批次(batches)，然后再以批次排序加工，使所有工件都交付所需的时间最短。所以该问题可以归结为一种需要先分批的排序。这种排序与经典的排序(或者称为“调度”)问题有很大的差异。因为即使对不分批的排序问题，求最短交付时间的最佳排序也是NP难解(NP-hard)问题。所以由此断定该问题更应该是NP难解问题。NP难解问题只能设计出近似算法(approximationalgorithm)，而课题组设计出该问题最好的近似算法，即多项式时间近似方案(PTAS，polynomial-timeapproximationscheme)，使课题组的算法可以在理论上无限靠近最优结果。该成果发表在2006年《应用数学》的第二期。课题组研究的第二个优化设计问题是WDM网络的路由与波长分配问题。课题组发现很多网络中的问题都可以转化为图论问题或组合优化问题。一个路由是连接两个通信节点的一条路(path)，如果对于很多对节点的通信请求(requests)，需要不同的通信请求之间若共享通信线路必须分配不同的波长(wavelength)。经过认真研究，课题组发现此问题可以转化为路的染色(pathcoloring)问题进行研究。课题组认真阅读了大量图论中染色理论的相关文献加以借鉴。课题组首先研究树状(tree)结构的网络，在树的顶点度数有限的情况下，课题组给出了最优的多项式时间算法。对于比树更复杂的环形树(treeofrings)网络，课题组设计了一个近似比为2的多项式时间的近似算法。课题组把该项成果提交到首届中国通信与网络国际会议，并在大会上宣读了课题组的研究成果，得到与会同行的好评。该论文在2007年被EI工程索引检索(检索号：074610922277)。第三个研究问题是网格中任务调度和带宽分配问题。通过研究国外的分布式计算技术，例如Condor系统，和并行计算技术，例如MPI系统。课题组发现以往的很多这方面的技术很少考虑带宽，如果把网格中节点的资源和节点间的带宽同时考虑进去，进行资源分配，就要考虑节点形成的拓扑结构，课题组认真研究了树状结构的网格计算如何分配资源和带宽。课题组首先从星状(star)简单结构开始研究，进而推广到一般的树状结构，给出了“随机舍入算法”和“去随机算法”。课题组2006年底出席了第五届国际网格与协同计算国际会议，并报告了课题组的研究成果。该结果同样被EI检索收录(检索号：080611078401)。