大规模集成电路预烧作业中分批排序问题的数学模型

摘要：

分批排序(Batch Scheduling)是在半导体生产过程的最后阶段提炼出来的一类重要的排序问题.单机分批排序问题就是n个工件在一台机器上加工,要将工件分批,每批最多可以同时加工B个工件,每批的加工时间等于此批工件中的最大的加工时间.Skutella[8]1998年把平行机排序的P||∑ωjCj和R||∑ωjCj表述成二次的0-1整数规划,得到一些令人满意的结果;国内罗守成等[9]、张倩[10]给出了单机排序问题1||∑ωjCj的数学规划表示,对于用数学规划来研究排序问题是一个很有意义的进展.本文首先介绍总完工时间和最小的带权单机分批排序问题1|B|∑ωjCj,然后将1|B|∑ωjCj表示成数学规划的形式,并且用数学规划中的对偶理论证明了SPT序是其特殊情况1|B＝1|∑Cj的最优解.

关键词：排序、分批排序、数学规划、总完工时间

所属期刊栏目：11

分类号：O223(运筹学)

资助基金：国家自然科学基金10271065

在线出版日期：2003-11-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：32-36