关于分批排序问题的研究

论文摘要

分批排序是近年来发展非常迅速的现代排序模型，有很强的应用背景。分批是将工件集分割成若干个字集，每一工件子集为一批，每批的工件放在一起加工，同批工件的完工时间均等于该批中最后工件的完工时间。目标是将工件分成若干批且排出各批的加工顺序，使目标值最优，分批排序模型按分批方式的不同分两大类：平行分批排序模型与继列分批排序模型，在平行分批排序模型中，机器在每一时刻可同时加工多个工件；在继列分批排序模型中，机器在每一时刻最多加工一个工件，工件是按照一个接一个串联的方式形成一批的。 多重指标排序作为一种多目标决策，在解决经济、管理、工程、军事等领域出现的复杂问题中起着越来越重要的作用，例如，在一个工厂的生产过程中，生产决策者不但想要使工件的总完工时间最小以减少生产费用，还要尽量使误工工件的个数最少，以更好地满足顾客的要求，多重指标排序的最优性规则是：求解具有κ重指标问题的最优解就是在对应的前k-1重指标问题最优解集合中寻找第κ单指标问题的最优解。近年来，多重指标的排序问题并不多见，李忠义等人在文献中给出了当第一指标是∑Cj，∑WjCj，Tmax及∑Uj时若干问题的算法和复杂性分析。 准时排序是一种经典的排序问题，已有很多研究结果。该模型的特点是工件不论是提前完工或推迟完工都产生不准时费用。 本文的内容分三大部分：第一部分提出了三种新型分批排序模型：（1）具有主次指标的单机分批排序问题（第二章）；（2）具有三重指标的单机平行分批排序问题（第三章）；（3）单机准时分批排序问题（第四章），对于这些问题的研究在文献中几乎没有见到，而这些模型具有很强的应用背景和理论研究意义，本文对这些新型排序模型给出了若干研究结果。第二部分对一些现有单机分批排序问题最优解的结构性质进行了系统研究（第五章）。对于分批排序结构性质的研究在文献中也没见到。第三部分研究了工件在限选机器上加工的若干平行机分批排序问题（第六章）。 在第二章中，本文研究了具有主次指标的单机分批排序问题，其主要结果如下：证明了带有到达时间、主指标为最大完工时间的两个问题是强NP-困难的：第一个是批容量有限制、次指标为总存储费用的平行分批排序问题；第二个是批容量无限制、次指标为最大延迟的继列分批排序问题。给出了三个批容量无限制问题的多项式时间算法：第一个是带有到达时间、主指标为最大完工时间、次指标为占用机器

论文目录

• 第一章 绪论
• §1 排序问题
• §1.1 机器排序模型
• §1.2 排序问题的分类
• §2 计算复杂性
• §3 分批排序问题
• §3.1 平行分批排序
• §3.2 继列分批排序
• §3.3 平行机分批排序
• §3.4 本文用到的主要已知结果
• §4 本文的主要结果
• 第二章 具有主次指标的单机分批排序问题
• §1 引言
• §2 主指标为最大完工时间
• §2.1 次指标为总存储费用
• §2.2 次指标为占用机器的总时间
• §2.3 次指标为最大延迟
• §3 主指标为最大延迟
• §3.1 次指标为最大完工时间
• §3.2 次指标为关于工件完工时间的任意正规函数
• §3.3 次指标为误工总数
• 第三章 具有三重指标的单机分批排序问题
• §1 第一指标为最大完工时间
• §2 第一指标为最大延迟
• 第四章 单机准时分批排序问题
• §1 引言
• opt|∑w_i∑_Jj∈B_i|L_j（B）|+w₀d_opt与问题1|b-in-1；batch；d_opt土△|∑w_i∑_Ji∈B_i|L_j（B）|'>§2 问题1|b-in-1；batch；d_opt|∑w_i∑_Jj∈B_i|L_j（B）|+w₀d_opt与问题1|b-in-1；batch；d_opt土△|∑w_i∑_Ji∈B_i|L_j（B）|
• opt|∑w_i∑_Jj∈B_i|L_j（B）|+w₀d_opt'>§2.1 问题1|b-in-1；batch；d_opt|∑w_i∑_Jj∈B_i|L_j（B）|+w₀d_opt
• opt土△|∑w_i∑_Ji∈B_i|L_j（B）|'>§2.2 问题1|b-in-1；batch；d_opt土△|∑w_i∑_Ji∈B_i|L_j（B）|
• j=d_opt|w_E∑E_j（B）+w_T∑T_j（B）+w₀d_opt'>§3 问题1|b-in-1；batch；d_j=d_opt|w_E∑E_j（B）+w_T∑T_j（B）+w₀d_opt
• j=d||L_j（B）|max'>§4 问题1|b-in-1；batch；d_j=d||L_j（B）|max
• 第五章 最优分批的结构性质
• §1 引言
• §2 最小化加权完工时间之和
• §2.1 继列分批模型
• §2.2 平行分批模型
• §3 最小化完工时间之和
• §3.1 继列分批模型
• §3.2 平行分批模型
• §4 最小化完工时间平方之和
• §4.1 继列分批模型
• §4.2 平行分批模型
• §5 最小化最大延迟
• §5.1 继列分批模型
• §5.2 平行分批模型
• 第六章 限选平行机分批排序问题
• §1 引言
• §2 一般子集族下继列分批模型
• §3 凸子集族下继列分批模型
• §4 一般子集族下平行分批模型
• 第七章 后记
• 参考文献
• 攻读博士期间完成的论文
• 致谢