柔性制造系统调度算法研究

针对混合流程调度的特性，研究了两台并行可替换机床的调度问题，在一个加工阶段内有两台机床并可相互替代加工，调度目标是使所有任务在这两台机床上的加工时间最短，这个问题已被证明为NP-hard问题。为此在分枝定界算法基础上提出了两个关于调度替换原则的推理，作为解决这类调度问题的基本原则。根据这两个推理给出了如何在这种混合流程调度中对任务排序及指定加工机庆的启发式调度算法，最后，通过仿真试验验证了该算法的有效性。     

两阶段混合流程调度问题研究

根据两阶段混合流程调度的特性，对于第一阶段有一台机床，第二阶段有两台并行可替换机床的调度问题，在分枝定界算法和Johnson规则的基础上提出了3种启发式优化调度算法，使得加工时间跨度最小，并根据不同的情况给出了判别算法效率的下边界，对这3种算法的优化效果进行了仿真试验，通过对大量计算结果的分析，分别得出了3种启发式算法的优化效果。     

机器有等待的工件具有区间限制两台同构并行机上批在线调度

研究两台同构并行机上的批在线调度问题,工件以批方式到达且每个批中有m个工件,每个工件的处理时间限定在一个区间上,只有当前批中工件全部加工完成后才可以加工其后面的工件,目标函数是使最大完成时间最小。针对这一问题,给出了1个批在线启发式调度算法,在同一批中的工件按LPT规则调度。对算法的最坏情况进行了分析并给出了算法的最坏情况比与批中工件数有关,并由计算机程序进行了验证。     

机器无等待工件具有区间限制的两台同构并行机上批在线调度

针对两台同构并行机上的在线批调度问题,提出了使工件加工的最大完成时间最小的一个批在线列表调度算法。即工件组成不同的批,每个批中有m个工件,当每批到达等待加工时,其内部的工件加工时间才已知,且每个工件加工时间限定在某个实区间[a,b]上。在对当前批后批中工件的信息不了解的情况下,立即将其中的工件按LPT规则调度进行调度,调度过程中不允许中断。解决了算法的可使用性的度量问题,对其最坏情况进行了分析,给出了算法的最坏情况比。     

车间作业的混合组合规则调度方法

分析多种类型零件投放车间时根据零件工艺路线特点，在不同机床上选用适当的启发式调度规则，实现车间调度周期内的多规则混合调度（ＭＤＲ－ＭｉｘｅｄＤｉｓｐａｔｃｈｉｎｇＲｕｌｅ）的方法。实验结果表明，针对具体加工任务和加工资源特点，通过有限步的仿真搜索所形成的多规则混合调度，算法性能比通常所采用的针对所有机床的单规则调度算法有明显提高。该方法已应用于作者开发的车间控制器中。     

解并行机提前/拖后调度问题的一种新并行遗传算法

针对交货期窗口非等同并行机提前／拖后调度问题,设计了一个基于向量组编码的新的遗传算法．此算法特点是编码方法简单,能有效地反映实际调度方案,即清楚反映出每台机器加工工件的代号和顺序,并能保证交叉和变异后个体自动满足约束条件,收敛速度快．同时为了更好地适应调度实时性和解大型此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法．仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性,并能适用于解大型这类调度问题．     

求解非标准作业车间调度问题的均衡算法

针对加工工序的设备是多台具有相同加工能力的机器集合的非标准Job-shop调度问题，利用指针队列及调度均衡的思想来构造目标函数，提出了非标准Job-shop调度算法．经过理论分析和实践验证，相对其他算法更加优化．     

基于改进蚁群算法的智能调度系统设计与开发

蚁群算法是一种模拟蚂蚁群体智能行为的仿生优化算法,具有良好的正反馈、鲁棒性、群体性和并行性等特点.在研究柔性作业车间调度的基础上,针对企业实际生产情况,将改进蚁群算法应用于求解实际生产调度问题.笔者介绍了智能调度系统的需求分析、系统设计和主要功能模块的实现.系统实现时采用事件驱动调度策略,当调度任务发生变化时根据上次调度结果重新调度,同时对蚁群算法做出适当改进,添加机器选择策略,在搜索解路径的过程中,首先确定下一步可供选择加工的工件在哪台机器上加工,然后确定加工哪个工件.开发的智能调度系统能完成企业的动态柔性调度,能较好的解决机器变化和订单变化引起的重调度问题,提高企业生产效率.     

一种新的Job-shop动态优化调度算法

针对具有路径柔性的Ｊｏｂｓｈｏｐ调度问题,以调度长度极小化为优化目标,提出了一种新的动态优化调度算法．该算法将优化分配算法、可行优化调度算法和故障（或修复）调度算法有机地集成起来,能够在系统设备出现异常（例如发生故障或修复等）时,迅速产生最优或次最优调度．并以机床发生故障及修复为例对该算法进行了仿真实验,证实了该算法的高效性和有效性．     

基于机器负载平衡求解非标准Job-Shop调度问题的算法

针对加工工序的设备是多台具有相同加工能力的机器集合的非标准Job—Shop调度问题，利用机器负载平衡的思想构造目标函数，提出了非标准Job—Sbop调度算法，经对工序加工过程的复杂性分析可知，该算法的时间复杂性较低，试验结果相对其他算法更加优化。     

A two-stage flexible flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage

This paper considers a hybrid two-stage flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage. The processing time of job Jj on any of m identical parallel machines is aj≡a （j∈N）, and the processing time of job Jj is bj（j∈N） on a batch processorM. We take makespan （Cmax） as our minimization objective. In this paper, for the problem of FSMP-BI （m identical parallel machines on the first stage and a batch processor on the second stage）, based on the algorithm given by Sung and Choung for the problem of 1 ｜ri, BI｜Cmax under the constraint of the given processing sequence, we develop an optimal dynamic programming Algorithm H1 for it in max {O（nlogn）, O（nB）} time. A max {O（nlogn） , O（nB）}time symmetric Algorithm H2 is given then for the problem of BI-FSMP （a batch processor on the first stage and m identical parallel machines on the second stage）.     

Dynamic Scheduling of Flexible Job Shops

Aim of this research is to minimize makespan in the flexible job shop environment by the use of genetic algorithms and scheduling rules. Software is developed using genetic algorithms and scheduling rules based on certain constraints such as non-preemption of jobs, recirculation, set up times, non-breakdown of machines etc. Purpose of the software is to develop a schedule for flexible job shop environment, which is a special case of job shop scheduling problem. Scheduling algorithm used in the software is verified and tested by using MT10 as benchmark problem, presented in the flexible job shop environment at the end. LEKIN software results are also compared with results of the developed software by the use of MT10 benchmark problem to show that the latter is a practical software and can be used successfully at BIT Training Workshop.     

机器带故障的两台机排序问题的一个近似算法

讨论机器带故障中断的两台平行机排序问题,目标为极小化误工工件数,在转移时间t=0时的排序问题是问题P2｜D=∞,t=0｜∑u′ij,该文给出了相应的算法,并利用该算法,考虑了当工件转移时间t〉0时的NP难的排序问题P2｜D=∞,t≠0｜∑u′ij。该文使用对前一问题的最优序π^＊当中的工件相交换,使得增加误工工件数尽量少的方法,提出了一个差界为1的多项式时间的近似算法,并给出了证明及算法的计算复杂性。     

流水车间调度问题的启发式算法研究

针对以完工时间最小为目标的流水车间调度问题,对问题的定义进行了全新的推导和分析,从数学的角度进一步挖掘出问题的本质特征.在控制第一台机器和最后一个工件加工时间的基础上,尽量压缩每个工件在加工前的等待时间,以提高算法的实际效果.模拟实验的结果表明,新的启发式算法具有很好的性能,使用新算法计算得到的调度序列平均质量以及算法本身的稳定性方面均明显优于与之具有相当算法复杂度的其他启发式算法.     

带单服务器的流水作业排序问题的复杂性

研究了一个带单服务器且加工时间相等的两机流水作业排序问题,其目标函数是使总完工时间达到最小.研究表明,该流水作业排序问题是强NP- 困难的.针对该流水作业排序问题构造了一种新的加工顺序,并证明该加工顺序的紧界为7/6.     

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

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

LPT算法的两个近似界估计

本文讨论带机器准备时间的平行机排序问题．由于它是ＮＰ－ｈａｒｄ的，我们讨论近似算法ＬＰＴ，研究它在使ｍａｋｅｓｐａｎ达到最小和ｍｉｎｉｍｕｍｃｏｍｐｌｅｔｉｏｎｔｉｍｅ达到最大两个目标下的近似程度．     

一类三阶段供应链排序问题的近似算法

主要研究一类三阶段供应链排序问题。储存工件的仓库和工厂在不同的地点,工件加工前需要从仓库运到工厂,加工完后再运回仓库。文中分别考虑了两个模型,第一个是两辆有容量限制的同类型车和单台机;第二个是一辆车和两台平行机。目标函数是极小化最后一个工件运回仓库的时间。针对两个模型,提出了相应的近似算法并证明其最坏情况界分别为2和2＋2λ-1^-1（其中λ〉1）。     

公共交货期窗口下提前/拖期多机调度的开工时间问题

随着JIT（Just-In-Time）生产管理技术的出现和发展，考虑零件提前／拖期费用的生产排序与调度问题已成为人们研究的热点领域。近几年有许多学者都研究了公共交货期窗口下提前／拖期多机零件排序问题，但所有机器都是零时刻同时开始加工零件的。本文通过例子分析说明，公共交货期窗口下提前／拖期都有惩罚的多机排序问题，所有机器都在零时刻同时开始加工零件并不一定能获得最小惩罚值。实际上，通过让某些机器在指定时刻后才开始加工，反而能获得更小的惩罚值。最后，本文提出一个确定指定机器的加工开始时刻的方法，具有很高的实际价值。