基于累计按期完工概率增量的一个排序算法

讨论工件加工时间为随机变量的单机静态列表排序极大化期望按期完工工件数问题。对于单机排序加工时间为独立同分布随机变量问题1／Xi-F／E∑Uj以及EXi≥EXjD di≤dj时，该文给出了预期按期完工工件和预期误工工件的最优划分算法。对于一般问题，对给定的置信度，该文采用倒序算法逐个剔除累计按期完工概率增量最大工件，完成预期按期完工工件集与预期误工工件集的划分，并以此为依据给出排序，最后通过搜索最优置信系数得出排序结果。     

窗时排序的计算机搜索算法

该文讨论按期完工工件数最大化的窗时排序问题。文章首先提出一个基于EDD序的枚举算法，很大程度降低了纯枚举算法的计算复杂性。然后以改进的枚举法作基础构造了一个启发式算法——遗传算法求解该问题。算法采用0-1编码，基于EDD序规则调整各个工件的排列顺序。该算法在处理大规模的单机排序问题时，能够在较短的时间内得到近似最优解。实例计算证明，该遗传算法近似程度好，可操作性强，可以在实际应用中推广。     

Moore-Hodgson算法的最优性

经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,是排序论中最基本的问题之一。著名的Moore—Hodgson算法可以在时间O（n log n）内得到误工问题的最优解。Pinedo在1995年对于Moore—Hodgson算法的最优性给出一个证明。虽然这个证明不严格,许多关键的地方交待不清,但是Pinedo证明的过程表明Moore—Hodgson算法得到解是所有最优解中不误工工件的总的加工时间最短的。这是一个很本质的性质,是其他所有的证明中没有提及的。本文补充和完善了Pinedo的证明。此外,对于推广的误工问题,例如,某些工件必须不误工的排序问题,或者工件的就绪时间不相同、但是与交货期有“一致性”关系的排序问题,或者工件的加工时间与工件的权有反向“一致性”关系的排序问题等,是否也有类似的性质？这是非常有意义的进一步研究方向。     

不误工工件加工时间之和最小的最优解

误工排序问题是经典排序论中最基本的问题之一。1968年Moore提出解决这个问题的算法,可以在时间O（nlogn）内得到最优解。误工问题推广到以下情况：或者某些工件必须不误工;或者工件的加工时间与工件的权有反向一致性;或者工件的加工时间与工件的权具有反向一致性,并且某些工件必须不误工等等。对于这些误工问题及其推广问题提出了多项式时间算法,证明了算法的最优性,并且证明了算法得到的最优解是所有最优解中不误工工件加工时间之和是最小的。     

误工工件个数最少的多目标排序问题

考虑在误工工件个数最少的约束条件下使得工件集合的总完工时间为最小的单台机器多目标排序问题.首先要使得误工工件个数∑Uj为最少,著名的Moore-Hodgson算法得到的排序就是一个可行解,并且该算法在遇到误工工件时总是尽可能把加工时间最长的工件放到误工工件集合L中,这也符合使总完工时间∑Cj为最小的目的.然而以往文献中的例子显示,这样得到的解并不总是最优解,这就暗示了该问题的复杂性,因此给出了不同于以往文献的分支定界算法及其Matlab解,简化了计算过程.     

带时间延迟的极小化总完工时间的单机排序问题

研究工件带有两道工序的单台机排序问题。在该问题中,工件的第一道工序先于第二道工序加工,并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间,目标是极小化所有工件的总完土时间。文章考虑所有工件相同且两道工序的加工时间均为单位时间的情形。通过引入忌一连续加工的概念和分析最优解的性质,根据延迟时间的大小,分别设计了两个算法并证明了算法所得的排序为最优排序。     

最小化完工时间和为第一目标的的多目标不相容分批排序

研究以工件总完工时间为第1目标的多目标不相容分批排序问题,对于加权总完工时间和最大延误为第2目标的排序问题给出了多项式时间的算法。对于误工工件个数和工件总延误为第2目标的排序问题的不同情况进行了讨论,给出了多项式时间算法或证明了其复杂性。     

加工时间线性递减的链约束单机排序问题

讨论了工件的加工时间是开工时间的线性递减函数、工件之间有平行链约束的单机排序问题.对于链可中断和不可中断两种情况,给出了极小化总完工时间的最优算法.     

具有公共交货期和提前—滞后惩罚的单机排序问题最优解的结构

求解具有公共交货和提前－滞后惩罚的单机排序问题是很困难的，其计算复杂性是强ＮＰ完全问题，作者研究这类问题的最优解的结构特征，得出了对于完工时间比公共交货期大的工件按ＷＳＰＴ序排列，对于完工时间少于公共交货期的工件按ＷＬＰＴ序排列，一般情况下的最优解具有Ｖ形结构的结论。     

具有学习效应的单机可控加工时间排序问题研究

在经典排序问题中,工件的加工时间往往是一个常数,但在现代生产过程中,工件的加工时间受许多因素的影响。因此,研究工件具有学习效应的单机可控加工时间排序问题,其中工件的加工时间是其所在位置的函数,且与加工时间的控制变量有关。目标是求出最优的加工时间控制变量和最优的排序使得目标函数最小,目标函数包括极小化时间表长与控制费用的和、极小化总完工时间与控制费用的和、极小化总完工时间偏差和与控制费用和。证明他们都能转化为指派问题,从而多项式时间可解。并给出数值例子来说明问题是如何求解的。     

一类工件有尺寸且分两次到达的在线分批排序

研究了工件有尺寸大小,有到达时间的在线分批排序,目标函数为工件的极大完工时间。就所有工件有2个到达时间的在线分批排序,给出算法,并证明了算法的竞争比不超过3。     

已知工件总加工时间的两台同类机半在线问题

研究了已知总加工时间的两台同类机半在线问题.假设工件是分别独立地到达加工机器,并且工件的总加工时间是已知的,目标函数为极大化最小机器负载.将总加工时间标准化后,给出近似算法及其竞争比,并证明此竞争比是紧的.给出此问题竞争比的一个下界1.6180,并由此推出当两台机器的速度比为1.618 0时,算法是最优的,算法的竞争比与最优算法的竞争比之差小于0.089.     

蚂蚁算法在工件排序问题中的应用

蚂蚁算法是近年来新出现的一类随机型仿生算法。它已被成功的应用于组合优化问题中,如旅行商(TravelSalesmanProblem,TSP)问题等。运用蚂蚁算法研究m台机器目标函数为最小时间表长的同顺序车间作业排序问题(Fm|prmu|Cmax),设计出解决该问题的算法步骤与流程;并将蚂蚁算法与解决该问题的其它启发式算法进行了比较。比较的结果说明,蚂蚁算法能有效地解决此类问题,其最优结果优于或者与其他算法的最优结果相当。     

带准备时间的平行机排序的LPT算法

本文考虑带准备时间的平行机排序问题，讨论在使最早机器完工时间达到最大目标下的优化问题．这是ＮＰ－ｈａｒｄ问题，本文证明ＬＰＴ排序解至少是最优解的倍．     

交货时间区间内完工工件个数最多的近似算法

在现代生产管理中,合理安排工件使所加工的工件准时交货是极其重要的,工件提前完工和延误完工都会增加费用,使尽量多的工件在其对应交货时间区间内完工的排序问题是NP困难的。本文讨论了m台平行机交货时间区间内完工工件个数最多的排序问题,给出了一个求解这一问题的多项式时间近似算法。     

JIT方式下的单机分批调度问题研究

准时生产意义下的调度问题，是当前调度领域研究的一个主要方面，针对单机分批作业准时生产方式，研究了不允许出现拖期的批调度问题，目标是使得加工总成本最小，目标函数不仅考虑了提高惩罚，还考虑了机器的加工费用，为了确定最优分批与各批次的开始时间，给出了两个推理的三个规则，并根据推理规则给出了一个有效的启发式算法，使得目标函数最小，应用实例说明了该算法的正确性与有效性。     

基于人工免疫-蚁群算法的平面QoS路由模型

人工免疫算法具有快速随机的全局搜索能力,但系统中的反馈信息利用不足且有大量无为的冗余迭代。蚁群算法具有分布式并行全局搜索能力,但初期信息素匮乏。本文提出一种基于人工免疫-蚁群算法的混合算法,采用人工免疫算法生成信息素分布,利用蚁群算法求优化解。将该算法用于求解包含带宽、时延和最小代价约束条件在内的平面QoS路由模型问题,进行计算机仿真。结果表明,该算法是一种收敛速度和寻优能力都比较好的优化方法。