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

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

误工排序问题的赶工分析

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

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

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

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

考虑在误工工件个数最少的约束条件下使得工件集合的总完工时间为最小的单台机器多目标排序问题.首先要使得误工工件个数∑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的多项式时间的近似算法。     

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

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

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

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

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

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

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

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

列队竞争算法求解多目的厂间歇过程调度问题

由于组合爆炸特性,多目的厂的调度问题很难求解大规模甚至中等规模的问题,本研究采用一种新的随机型进化搜索算法——列队竞争算法对该问题进行求解,引入新的选择策略和变异方法。计算表明,同已有的方法相比,该方法求解效率高、收敛速度快、使用简单方便,可有效的克服计算负荷和求解质量之间的冲突,是一种求解多目的厂间歇过程调度问题的有效算法。     

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

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

带有动态到达工件的分布式柔性作业车间调度问题研究

分布式柔性作业车间调度是生产调度的1个重要分支,工件的动态到达作为实际生产中的1种常见扰动情况,进一步增加了作业车间调度问题的复杂性和不确定性。针对带有工件动态到达的分布式柔性作业车间调度问题(DA-DFJSP),提出1种分批调度策略,将原本的动态调度问题转化成一系列连续调度区间上的静态调度问题,构建以最大完工时间为优化目标的混合整数规划模型;在此基础上,结合问题特征采用批次、工厂、工序、机器的4层染色体编码及快速贪婪搜索插入的解码方式改进遗传算法,同时引入多种交叉、变异算子来增强染色体的多样性;最后,基于FJSP标准算例构建DA-DFJSP测试算例进行仿真对比实验,验证所提策略和改进算法的求解优势。结果表明：相较于传统的重调度策略和改进前的遗传算法,采用分批调度策略和改进的遗传算法(IGA)所求调度方案具有更短的完工周期、更均匀的工厂加工负荷及更高的设备工作效率,IGA与分批调度策略之间有高度的契合性,能够有效提升生产效率。     

带两个服务等级约束的三台机排序问题

研究带两个服务等级约束的3台同型机在线排序问题。工件和机器的服务等级为1或2,加工允许中断但不允许引入机器空闲时间,目标是最小化最大完工时间。该文首先证明任意在线算法的竞争比至少是3/2,接着对仅有1台机器等级为1的情形给出了竞争比为5/3的在线算法。