摘要
分批排序(BatchScheduling)是在半导体生产过程的最后阶段提炼出来的一类重要的排序问题。单机分批排序问题就是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的最优解。
We study the problem of minimizing total weighted completion time on single batch processing machine.It is a problem of batch scheduling which arises in the burnin stage of semiconductor manufacturing.Burnin ovens are modeled as batchprocessing machines which can handle up to B jobs simultaneously.The processing time of a batch is equal to the longest processing time among the jobs in the batch.In 1998,Skutella formulated the parallel machine scheduling problem P||∑ωjCj and R||∑ωjCj as 01 mixed integer programming.Luo and Zhang formuated the single machine scheduling problem 1||∑ωjCj as mathematical programming.We first formulate the problem of minimizing total weighted completion time on single batch processing machine 1|B|∑ωjCj and get some conclusions.
出处
《中国管理科学》
CSSCI
2003年第4期32-36,共5页
Chinese Journal of Management Science
基金
国家自然科学基金资助项目(10271065)
关键词
排序
分批排序
数学规划
总完工时间
scheduling
batch scheduling
mathematical programming
total competion time
