Moore-Hodgson算法的最优性

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

推广的误工排序问题的最优算法

研究了工件的就绪时间可以不相同、但是与交货期有“一致性”关系,并且在保证工件的一个子集T中的工件必须不误工的前提下,使误工工件的个数为最少的推广的误工排序问题1｜T,（ri≤rj）=〉（di≤dj）｜∑Uj。提出该问题的最优算法,并且用孙叶平等人证明误工排序问题1｜（ri≤rj）=〉（di≤dj）｜∑Uj最优性的方法,证明了提出的算法得到的排序是最优排序。     

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

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

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

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

加工时间可控的同时加工排序问题

同时加工排序和可控排序是两类很重要的现代排序模型,有着深刻的实际背景和广阔的应用前景,已经取得许多有意义的成果,然而,还没有看到把两者结合起来的研究。把这两类排序模型相结合,讨论加工时间可控的同时加工排序问题:工件可以有不同的加工时间,每个加工时间对应一个控制费用,所有工件在单台机器上平行同时加工,即同时加工的一批工件的加工时间等于这批工件中所有工件加工时间的最大者;分别使误工工件个数和最大延迟加上加工时间可控所需费用的总和为最小作为优化的目标。讨论了这两个问题的最优解的性质,并以此为基础提出了相应的动态规划算法。     

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

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

在误工工件个数最少的条件下使最大延误为最小的分支定界算法

多目标排序是研究多个优化目标的排序问题,在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。2007年有文献证明以误工工件个数最少为第l目标、使总完工时间最小或者使总延误最小的多重目标排序问题1‖（∑Cj／∑uj）或者1‖（∑Tj／∑Uj）都是NP困难的。然而,迄今为止,对于以误工工件个数最少为第1目标、使最大延误最小的多重目标排序问题1‖（Tmax／∑Uj）的计算复杂性还不清楚。给出了这个多重目标排序问题1‖（Tmax/／∑Uj）的分支定界算法,借助几个性质,得到较好的上下界,能够较快地得到最优解。     

期望按期完工工件数最大化算法研究

该文讨论工件加工时间为随机变量的单台机排序极大化期望按期完工工件数问题。在确定性排序问题中，Moore算法给出问题的最优解，但事实上Moore算法的期望值版本不能给出期望按期完工工件数最大化问题的最优解。文章从研究排序中工件的按期完工置信系数人手，结合Moore算法，提出了一个启发式算法，有效地解决了该随机排序问题的实际计算。     

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

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

误工排序问题的赶工分析

本文研究误工排序问题的赶工分析，对排序问题的实际应用和可控排序的理论发展具有一定的意义。文中采用分支定界法来搜索这个ＮＰ难题的最优解。由于考虑工件间的优先关系，往往可以减少分支，很快得到最优解。     

单机分族分批排序的最小误工个数问题

文章研究了同一族内,给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O（mb（n/m）^2m）的动态规划算法。     

工件带链约束和尺寸的并行批排序

主要对带链优先约束和尺寸的工件并行批排序问题进行了研究,当工件的加工时间一致时对目标函数是极小化所有工件加工时间之和的情形,借助于拆分的技巧,给出了一个最差性能比为2的近似算法.     

An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times

Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutually independent and available at time zero. The machine processes the jobs sequentially and it is not idle if there is any job to be processed. The operation of each job cannot be interrupted. The machine cannot process more than one job at a time. A setup time is needed if the machine switches from one type of job to another. The objective is to find an optimal schedule with the minimal total jobs' completion time. While the sum of jobs' processing time is always a constant, the objective is to minimize the sum of setup times. Ant colony optimization (ACO) is a meta-heuristic that has recently been applied to scheduling problem. In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation (DPBAC) algorithm for the single-machine scheduling problem. DPBAC improves traditional ACO in following aspects: introducing Branching Method to choose starting points; improving state transition rules; introducing Mutation Method to shorten tours; improving pheromone updating rules and introducing Conditional Dynamic Perturbation Strategy. Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.     

An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times

Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro- cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs'completion time.While the sum of jobs'processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul- ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im- proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc- ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.     

极小化最大提前完工时间的单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.基于此,讨论了带准备时间和强制工期的n个工件在单机上加工,在机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,考虑了工件加工时间相等的特殊情形.先讨论问题的可行性,针对可行问题,提出了一个算法在多项式时间内获得最优排序.     

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

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

工业生产中一个带有拒绝费用的工件排序问题研究

在工业生产中,生产决策者为了获得最大利润,可能接收一个工件,也可能拒绝一个工件.为了解决哪些工件应该被接收,哪些工件应该被拒绝问题,本文研究了工业生产中一个带有拒绝费用的工件排序问题,对该问题设计了一个动态规划算法.