成组排序中确定公共交货期使误工件数最小问题

本文讨论的问题是在单台机器成组加工中为已经到达的工件集确定公共的交货期和工件的加工顺序，使因确定交货期所化代价和因误工造成的损失之和为最小。本文对满足成组技术假设和不满足成组技术假设这两种情况分别给出寻找最优解的多项式算法。     

误工排序问题的赶工分析

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

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

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

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

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

“合成链”算法与一类链优先约束的单机分批排序问题

讨论问题1|chains,B|Cmax具体可描述为:有n条链,其中一条链上有n个工件,其余的n-1条链上的工件数之和为常数k,且工件的加工时间不限制,目标函数为最大完工时间。我们对该问题B=2的情况进行了深入的探讨,在研究过程中首次提出"合成链"算法,给出了时间复杂性为O(nk))的多项式时间算法     

机器带中断的误工问题的近似排序算法

该文讨论两台平行机排序问题,其中一台机器在不确定情况下中断,中断持续时间为D,目标为极小化误工工件数。当工件转移时间T=0时,该文提出该问题的最优算法。当转移时间T>0时为NP难问题,该文提出了一个差界为1的多项式时间的近似算法。     

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

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

工件可拒绝的单机无界平行批排序

首次考虑了目标函数为极小化最大延误与被拒绝工件的惩罚费用之和的单机无界平行批排序问题.证明了问题1｜B≥n,rej｜ Tmax+ TCP为NP-困难的,针对该问题给出了基于动态规划的伪多项式时间算法.     

成组排序中确定公共交货期使误工工件数最小问题

本文讨论的问题是在单台机器成组加工中为已经到达的工件集确定公共的交货期和工件的加工顺序，使因确定交货期所化代价和因误工造成的损失之和为最小。本文对满足成组技术假设和不满足成组技术假设这两种情况分别给出寻找最优解的多项式算法。     

赋有提前或延误惩罚的单机排序问题的动态规划算法

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明：赋有延误惩罚的单机排序问题是强ＮＰ－完全问题,没有多项式时间算法。笔者曾证明＾「２」;如果附加条件ｐｉ≥ｐＪ≥ｐｉ／ωｉ〉ｐｊ／ωｊ对于所有的ｉ≠ｊ（ｉ,ｊ＝１,２…,ｎ）成立,则该问题有伪多项式时间算法。现在研究如何用动态规划方法求解这类排序问题。     

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

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

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

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

单台机器总完工时间随机排序问题的反问题

运筹学和最优化的种种问题(“正问题”)是在已知各有关参数或者数据的条件下,找出最优(最快、成本最省或者效益最大)的方案。所谓的“反问题”,是指已经有一个方案,但在目前的情况下,该方案并非最优,需要考虑如何最小限度地改变现有参数,使这个方案成为最优的方案。如果说“正问题”的研究有助于一个新系统的设计和确定,那么“反问题”的研究对改善现有系统的性能具有重要的意义。文章以数学规划为工具,研究单台机器以带权总完工时间为优化目标的随机排序问题1‖∑E(wjCj)关于加工时间分布参数的反问题,并给出不带权的情况1‖E(∑Cj)的反问题及其最优解。     

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.     

工件可拒绝排序问题的线性规划松弛算法

研究了工件可拒绝排序问题．考虑目标函数是拒绝费用与带权总完工时间之和，应用线性规划松弛方法设计了近似算法，当工件之间没有优先关系时得到3-近似算法，当工件之间具有优先关系时得到4-近似算法.     

工件可拒绝排序问题的线性规划松弛算法

研究了工件可拒绝排序问题.考虑目标函数是拒绝费用与带权总完工时间之和,应用线性规划松弛方法设计了近似算法,当工件之间没有优先关系时得到3-近似算法,当工件之间具有优先关系时得到4-近似算法.