分批排序问题

【作者】 刘丽丽；

【导师】 张玉忠；

【作者基本信息】 曲阜师范大学 ， 运筹学与控制论， 2000， 硕士

【摘要】 分批排序问题是在半导体生产过程中提炼出来的一类重要的排序问题，它一般可被描述为： 有固定的n个工件要在一台或多台机器上加工，其到达时间和工时不一，要将工件分批加工，每批最多加工固定数目(一般记为B)个工件，把每批看作一个工件，其到达时间和工时分别是此批中所有工件的到达时间和工时的最大者，我们如何对工件进行分批，如何安排各批的顺序使问题的目标函数值最优． 本文共分三章，第一章介绍排序和分批排序问题的产生背景及一些基本的相关知识．第二章针对工件有不同大小(用a_i表示，i=1，2，…n)、以最大完工时间为目标函数的分批排序问题，首先证明了R.Uzsoy给出的FFLPT算法的性能指标，修正了算法FFSPT，给出了平行机情形的两种近似算法PFFLS和PFFLPT，并分别给出了它们的性能指标．第三章主要讨论了当B≥n时，工件有到达时间的几个分批排序问题，通过二划分问题的多项式归结证明了l|B≥n，r_i|sum(T_i)，问题，l|B≥n，r_i|sum(U_i)问题及l|B≥n，r_i|sum(C_i)问题的NP-完备性．更多还原

【Abstract】 SHEDl LING PROBLEMS ON BATCHING MACHINEABSTRACT: The model of our problems is motivated by the problem of scheduling burn-in operations for large-scale integrated circuit manufacturing. The paper mainly includes three chapters, some relating background information about scheduling and batch scheduling is introduced in Chapter l.The main result comprises two parts : Chapter 2 and Chapter 3.In Chapter 2.we discuss the problem of scheduling jobs with non-identical job sizes to minimize makespan on single and parallel batch processing machines .those problems are all NP-Complete obviously .we analyze the performance ratio of algorithm FFLPT developed by R.Uzsoy. that is 2.improve algorithm FFSPT and prove its worst-case performance ratio is also 2.As to the parallel machines .we provide two heuristic algorithms (PFFLPT and PFFLS) and prove their performanceratios are and 3 respectively. In Chapter 3.suppose thebatching machine can handle up to B jobs simultaneously, we analyze the unbounded model (i.e. B >n land jobs with unequal release dates, prove theproblems , and , are all NP-Complete through polynomial reduction from the partition problem respectively.更多还原