多目标分批排序及其相关课题

论文摘要

在过去的50年中,机器排序问题已成为组合最优化中最活跃的研究课题之一。然而,在大多数经典的排序文献中,只考虑机器一次至多加工一个工件,且目标函数只有一个。随着时间的推移,分批排序和多目标排序已蓬勃发展起来。可是将两者（分批排序和多目标排序）结合起来的研究尚不多见。由于电子加工业及其它产业的高速发展,以及决策者的不同利益需求,将分批排序与多目标排序结合起来考虑,应该提到议事日程上。设n个无关的工件J1,J2,…,Jn,它们将在一台分批处理机上加工。工件Jj的加工时间、工期、期限和权分别为pj、dj、（?）j和wj（j=1,…,n）。以Sj和Cj分别表示工件Jj的开始加工时间和完工时间。给定一个序σ,Lj（σ）=Cj（σ）—dj与Lmax（σ）=maxj=1nLj（σ）分别表示工件Jj的延迟与序σ的最大延迟。Tj=max{0,Lj}为工件Jj的延误,Uj为它的单位惩罚因子。本论文主要考虑分批处理机上同时最小化双目标排序问题。所谓的分批处理机是指机器可同时加工多个工件,放在一起加工的工件集称为一批,同一批中的工件具有相同的开工时间和完工时间。根据批的加工时间的不同定义,分批处理机又分为平行分批处理机和序列分批处理机。对前者,一批的加工时间等于这一批中最长工件的加工时间。这一模型是由半导体加工的烘烤、计算机系统及其它领域的操作抽象而来的。对后者,一批的加工时间等于这一批中所有工件的加工时间之和,且在每一批加工开始前,都有一个常数s的安装时间。这一模型起源于现实生活中这样的要求:当一批工件加工完成后,需要一段时间来调换工具、维修机器等。另一方面,两个目标函数可以代表两个决策者的不同利益。这一方向发展的基本动机源于这样的事实:质量评估通常是一个多维概念。并且决策者常常追求多个目标同时最优化一对所有目标函数找出全部的Pareto最优序。称一个可行序σ是关于目标函数f和g的Pareto最优序,是指不存在可行序π,使得f（π）≤f（σ）,g（π）≤g（σ）,且其中这两个不等式至少有一个严格成立。本学位论文的主要研究成果如下:1.单机平行分批的双目标排序前人分别对双目标及平行分批两方面已得到一些结果。例如,证明了同时最小化最大延迟和最大费用函数的单机排序问题可在O（n3log n）时间内解决。在平行分批处理机上,当机器容量无界时,最小化最大延迟问题已有O（n2）时间的动态规划算法。而我们考虑两方面的结合,即同时最小化最大延迟和最大完工时间的平行分批排序问题,并给出一个O（n3）时间的多项式时间算法,可以求出全部Pareto最优解。对多目标优化问题而言,求出全部Pareto最优解是最完整的解答。另外,当机器容量有界,且工件的加工时间为常数时,以总延误为主指标,次指标分别是误工工件数、加权误工工件数和加权总完工时间的分层最小化问题已有O（n3）时间算法。我们统一地给出O（n log n）时间算法,改进了上述时间界。2.单机序列分批的双目标排序对于序列分批的单目标排序问题,当机器容量无界时,最小化最大延迟问题已有O（n2）时间的算法;最小化加权总完工时间也已有了O（n）时间的算法。对于双目标问题,没有已知结果。我们在O（n2）时间内解决了同时最小化最大延迟和最大完工时间问题。此外,对同时最小化最大完工时间和总完工时间问题,在机器容量无界或有界的情形下,我们分别给出O（n2）时间算法。以上算法均可求出全部Pareto最优解,获得完全的解答。3.单机双目标排序已知最小化具有截止时间的误工工件数问题是NP-困难的。对如下特殊情形的误工工件数问题,文献中已有O（n2）时间的后向算法。（ⅰ）如果dj≤dj,那么（?）i≤（?）j与Pi≤Pj;（ⅱ）如果Pi≥pj,那么di—dj≤pi—pj。为建立统一的理论,我们提出了一种对偶算法一前向的贪婪算法,对情形（ⅰ）,它有更好的时间界O（n log n）。对情形（ⅱ）,得到相同的时间界,但方法有不同特点。并且我们还研究了工件加工时间相等的情形,也找到了O（n log n）时间算法。因为不同的决策者对同一个工件的工期要求可能不同（它们分别代表各自的期望利益）,所以可设每一个工件Jj具有两个工期dj（1）和dj（2）（1≤j≤n）。这样,对一个给定的序σ,就诱导了两个目标函数最大延迟Lmax（1）与Lmax（2）。我们证明同时最小化关于两个工期集合的最大延迟问题可在O（n3 log n）时间内解决,求出全部Pareto最优解,且时间界是紧的。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 排序论的学科特点
• 1.1.1 发展概貌
• 1.1.2 模型分类
• 1.1.3 基本概念与术语
• 1.2 排序论的两个发展方向:分批排序与多目标排序
• 1.2.1 应用动机
• 1.2.2 分批排序
• 1.2.3 多目标排序
• 1.3 已有研究工作进展
• 1.4 本论文研究工作简介
• 第2章 单机平行分批的双目标排序
• 2.1 引言
• max,C_max)-Pareto最优化'>2.2(L_max,C_max)-Pareto最优化
• 2.2.1 问题表述
• 2.2.2 最小化最大完工时间和最大延迟
• jT_j,*）-分层最优化'>2.3（∑_jT_j,*）-分层最优化
• 2.3.1 问题表述
• 2.3.2 最优性的特征
• 2.3.3 贪婪型算法
• 第3章 单机序列分批的双目标排序
• 3.1 引言
• max,C_max)-Pareto最优化'>3.2(L_max,C_max)-Pareto最优化
• 3.2.1 问题表述
• 3.2.2 多项式时间算法
• max,∑_j=1ⁿC_j)-Pareto最优化'>3.3(C_max,∑_j=1ⁿC_j)-Pareto最优化
• 3.3.1 问题表述
• 3.3.2 动态规划算法（DP算法）
• 3.3.3 有界模型
• 第4章 单机双目标排序
• 4.1 具有截止时间的问题
• 4.1.1 引言
• 4.1.2 一致性数据的情形
• 4.1.3 带凸性条件的情形
• 4.1.4 加工时间相等的情形
• 4.2 具有双工期的问题
• 4.2.1 引言
• 4.2.2 寻求Pareto最优解
• 参考文献
• 攻读博士学位期间发表的论文
• 致谢