带运输机的流水车间调度的最优算法

研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n~2)的最优算法.     

粒子群遗传混合算法求解考虑传输时间的FJSP

在某些生产制造场景中,工件在不同机器间的传输时间对车间调度的总拖期具有重要影响,本文基于此扩展了总拖期最小的柔性作业车间调度模型。针对问题模型的复杂性,采用粒子群优化算法和遗传算法的混合算法进行求解。在初始化过程以一定概率优选加工时间和传输时间短的机器并排除调度频繁的机器,使种群在保持多样性的前提下尽量选择优化结果好的个体;采用线性调整的方式动态改变交叉概率和变异概率的值,使种群在遗传算法的不同阶段具有不同的搜索强度;采用粒子群优化算法进行局部搜索,弥补了遗传算法局部搜索能力的不足。最后采用本文方法和其他方法求解柔性作业车间调度问题实例,并对比不同水平层次传输时间下的总拖期,验证了本文方法的有效性。     

具有负载依赖型维护时长的平行机调度问题

本文考虑具有工具更换的平行机调度问题,机器的维护时长依赖于维护前的负载,目标为最小化时间表长.首先,基于维护时长函数为单调不减函数得到最优调度方案应有的两个性质——单台机器加工的工件个数最多相差一个;每台机器在最后一个维护间隔应尽可能多地加工工件.其次,对维护时长函数为凹函数、凸函数和线性函数的情况分别给出算法MNJF, SJF和SLE.最后,证明算法MNJF, SJF以及SLE均为对应情况的最优算法,且算法MNJF对于维护时长函数为线性函数的情况也是一种最优算法.     

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。     

具有非对称模糊加工时间工期指派调度优化问题的一类加权模型及其求解算法

根据模糊变量截集所表达的信息的重要程度,建立了模糊环境下工期指派调度优化问题的一类加权模型,该模型中工件加工时间为非对称三角模糊数,目标函数为极小化提前完工惩罚和拖期完工惩罚和的加权可能性均值.证明了当工件加工时间具有相同宽度比时,模型是多项式可解的,并给出了求解的多项式算法.数值实验表明加权模型与现有的非加权模型相比能有效的降低总费用.     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

考虑运输时间的MapReduce模型下的同类机调度研究

MapReduce模型在大数据处理及机器调度方面日趋重要.针对MapReduce模型中的每个工件由Map和Reduce两道加工工序组成,其中Map工序允许分割成若干个子任务,并在多台同类机上并行加工,而Reduce工序只能在该工件的Map工序里的子任务全部加工完后才能启动加工,且Reduce工序不能分割,即只能在一台机器上连续加工.在实际生产中,重型工件的两个相邻工序若分配给不同机器,则工件在机器之间需要一定的运输时间.结合工件的到达时间约束,以最小化最大完工时间为目标,构建了混合整数规划模型,设计了采用单纯形差分变异策略的改进磷虾算法来求解模型.利用数值仿真实验,与基本磷虾算法、遗传算法及CPLEX计算结果进行对比.测试结果说明了所提出的改进磷虾算法在解的质量和运行时间方面均优于基本磷虾算法、遗传算法,验证了模型与算法改进的有效性.     

急件订单干扰下虚拟单元重调度

虚拟单元生产中,针对急件订单干扰情况,研究了考虑序位相似性,即尽量保持初始工序的加工次序的虚拟单元重调度问题。为了应对急件订单干扰,设置了各工件工序可用机器集合和相应的加工时间集合,构建了以序位相似性最大和急件订单完工时间、系统总流程时间最短为目标的多目标非线性整数规划模型。针对模型自身特征,采用了遗传—蚁群算法相结合的优化算法求解模型。最后,以船舶实际生产为例,验证了模型的可行和优越性,以及算法的有效性。     

汽车4S店维修车间的优化调度分析

调度研究的问题是将稀缺资源分配给在一定时间内的不同任务,它是一个决策过程,其目的是优化一个或多个目标。对实际问题的优化调度可以帮助企业提高资源利用率,减少客户等待时间,提升竞争力,对汽车4S维修服务站的优化调度问题进行研究,剖析这一实际应用问题的调度目标、机器环境、加工特征和约束等细节,提出了优化调度模型,设计了调度算法。然后,通过实例,简要分析了模型及算法的可行性.     

考虑部分工件不可打扰的多任务调度问题研究

多任务调度问题存在于各种应用领域,如因特网服务领域,医疗领域等。经典的多任务调度模型中所有工件均可被其他等待工件打扰,且仅打扰一次。然而在生产实践过程中,有些紧急工件是不允许被其他工件打扰。在此启发下,对原有模型进行扩展,研究了在单机多任务环境下部分工件不可打扰的调度问题,模型目标包括最小化最大完工时间,最小化总完工时间,最小化最大延迟以及最小化加权提前期、拖延期和共同交货期之和。对于前三个目标给出了精确算法,对于最后一个目标给出了启发式算法。最后,对今后的研究提出了建议。     

A green train scheduling model and fuzzy multi-objective optimization algorithm

Train scheduling model is traditionally formulated to minimize the energy consumption for reducing the operation cost. As the European Union formulates the first carbon emission trading scheme in the world, it is necessary to extend the operation cost to include the expenses for buying/selling the carbon emission allowances. In this paper, we propose a multi-objective train scheduling model by minimizing the energy and carbon emission cost as well as the total passenger-time, and named it as green train scheduling model. For obtaining a non-dominated timetable which has equal satisfactory degree on both objectives, we apply a fuzzy multi-objective optimization algorithm to solve the model. Finally, we perform two numerical examples to illustrate the efficiency of the proposed model and solution methodology.     

具有学习效应的半导体晶圆制造绿色车间调度问题研究

针对最小化最大完工时间、总碳排放以及总拖期时间的具有学习效应的半导体晶圆制造绿色车间调度问题,构建了双影响因素的新型学习效应模型,提出了改进的多元宇宙优化算法,并对其收敛性进行证明。通过对初始种群进行反向学习、宇宙个体进行莱维飞行扰动和对外部档案中的个体进行邻域搜索变异更新,产生新的父代个体,扩大了种群的多样性,避免算法陷入局部最优。通过对小规模和大规模测试算例的仿真实验,以及利用改进算法求解具有异质性机器的学习型半导体晶圆制造绿色车间调度问题,验证了本文所提出的算法对于求解具有学习效应的半导体晶圆制造绿色车间调度问题的有效性和可行性。     

具有周期维护最小化时间表长的两台平行机调度问题(英文)

本文讨论了具有周期维护的两台平行机调度问题,目标函数为最小化时间表长.设T为维护周期,t为每次对机器维护需要的时间,当t≤T/3时,本文证明了对于该问题由LPT算法得到的最坏误差界为2.     

Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function

The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are used. Both the preemptive and the nonpreemptive cases of the problem are considered.     

Scheduling flexible machining and assembly systems

Most scheduling papers consider flexible machining and assembly systems as being independent. In this paper, a heuristic two-level scheduling algorithm for a system consisting of a machining and an assembly subsystem is developed. It is shown that the upper level problem is equivalent to the two machine flow shop problem. The algorithm at the lower level schedules jobs according to the established product and part priorities. Related issues, such as batching, due dates, process planning and alternative routes, are discussed. The algorithm and associated concepts are illustrated on a number of numerical examples.     

两台同类机排序问题SPT算法的最坏情况比

本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。     

两台同类机排序问题SPT算法的最坏情况比

本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。     

Scheduling incompatible tasks on two machines

The paper studies the problem of scheduling tasks on two machines to minimize the makespan. The tasks are assigned to the machine in advance. An incompatibility relation is defined over the tasks which forbids any two incompatible tasks to be processed at the same time. The problem can serve as a mathematical model for some batching problems in which the jobs are grouped in pairs on two machines. A linear-time algorithm is presented.     

Makespan minimization for parallel machines scheduling with multiple availability constraints

The problem of makespan minimization for parallel machines scheduling with multiple planned nonavailability periods in the case of resumable jobs is considered. In the current state of the literature, there is a limited number of models and algorithms dealing with this problem and only for very small problem size, and nonavailability limited to some machines. The problem is first formulated as a mixed integer linear programming model and optimally solved using CPLEX for small to moderately large size problems with multiple availability constraints on all machines. An implicit enumeration algorithm using the lexicographic order is then designed to solve large-scale problems. Numerical results are obtained for several experiments and they show the validity and performance improvements procured by both the MILP model and the new enumeration algorithm.