具有优势机器和恶化工件的流水作业排序问题

针对流水作业排序问题,建立了具有优势机器和恶化工件并且有无空闲限制的排序模型.在该排序模型中,机器加工工件时,工件的相邻加工工序之间不允许出现空闲,工件的加工时间是其开工时间的严格增加线性函数.其中讨论的优势机器有2种情况:机器形成增减增优势关系和机器形成减增减优势关系.考虑了多台机器的流水作业排序问题,其中,目标函数分别为极小化最大完工时间和极小化总完工时间,对于这两类问题分别给出了求解最优排序的多项式算法和它们的计算复杂性,并通过证明证实了算法的有效性.     

带强制工期的单机排序问题

讨论了带强制工期的n个工件在单机上加工,在允许机器空闲的条件下,使得最大提前完工时间最小。由于工件不允许延迟,问题可能会无可行排序。先讨论问题的可行性。如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后判断预排序列是否为最优,如果不能直接确定为最优,则给出一个算法在多项式时间内尝试由预排序列开始,通过不断调整工件的次序来获得最优排序。     

一类带有安装时间的单机成组排序问题

针对一类带有准备时间和安装时间的单机成组排序问题,给出了求解最优排序的多项式算法。其中每个工件都具有自己的准备时间,组和组之间具有安装时间,并且安装时间和已经加工完工件的加工时间有关。所有工件在机器上加工时,一次只能加工一个工件,工件不可中断,组内工件连续加工,组和组之间需要安装时间。对目标函数为极小化最大完工时间的单机成组排序问题,给出了求解最优排序的多项式算法。原问题不是成组问题,为此在原问题的基础上添加了工件的成组问题且组内每个工件都具有自己准备时间,其结果是依然能给出求解最优排序的多项式算法。     

加工时间线性递减的平行机排序问题

主要讨论了具有两台处理机的平行机排序问题和每批恰为k个工件的串行工件同时加工排序的平行机排序问题。在这两个问题中,工件加工时间均为开工时间的线性递减函数,目标函数为极小化总完工时间。对于第一个问题,证明了其最优排序可由工件按基本加工时间不减排列得到,由此得出其最优算法,并指出了该结论对于加工时间随开工时间线性递增的情况并不成立。对于第二个问题,根据其与第一个问题在某些性质上的相似性,给出了其最优算法。最后指出所讨论的两个问题的结论均可推广到m台处理机的情况。     

考虑搬运时间的多品种、小批量混流制造系统批量加工模式的优化与资源调度

对带搬运时间的混流制造系统批量加工模式的优化与资源调度问题进行研究. 建立批量工件的加工与搬运时间模型,用于求解生产周期和优化搬运次数. 在此基础上,分析工件排序方案的决策准则,用于确定工件最优投产顺序. 设计互助组优化算法,其可对最优作业排序方案所需的搬运设备进行调度. 研究结果表明: 本文的研究方法可有效求解带搬运时间的批量工件的生产周期,能优化批量工件的搬运时间和次数,可获得工件的最优排序方案,并能合理调度搬运设备资源.     

等待时间受限的流水车间调度问题的若干性质

等待时间受限的流水车间调度问题广泛存在于高温连续作业或中间产品不稳定的流水车间生产管理过程中, 要求工件在相邻机器上的等待时间不能超过一定的上限. 针对以最小化最大完工时间为目标函数的该类问题, 研究了加工机器上的工件序列特征, 并在此基础上分析了基于排列排序进行问题求解的可行性和有效性, 为算法求解提供了理论依据.     

求解并行加热炉群调度问题的三阶段算法

针对并行加热炉群调度问题,提出了以板坯的最大完工时间和炉内总停留时间最小化为目标的求解算法.算法由3个阶段组成:第1阶段以关键路规则为基础确定板坯排序,在一定条件下具有最优性;第2阶段对任意给定的板坯排序,给出该排序下关于炉内总停留时间的最优可行排序;第3阶段对任意给定的可行板坯排序,给出该可行板坯排序下满足板坯释放时间的最优调度方案.     

考虑最小化最大完工时间间隔的三台平行机调度

针对平行机调度,研究了当无预知情况下应对紧急任务快速响应的一类加工方案.考虑三台平行机的加工环境,分析任意两个相邻的工件完工时间的间隔,以最小化最大间隔值为优化目标.首先给出机器完工时间的两个上界作为可行方案的充分条件,进而给出最优方案的基本性质;其次,基于最优解的性质证明了目标值的一个下界并设计了 O(n~2)时间的算法来求解该下界值;最后运用预留尽可能多的空闲时间(RMST)在一台机器上的思想,设计了改进的RMST算法(IRMST)来求解该问题.通过利用数值仿真实验与RMST算法,遗传算法等其它算法及下界进行对比,验证了该算法的有效性.     

用遗传算法求解机器排序优化问题

提出一种针对机器排序问题的遗传算法,该算法编码简单并构造了新的交叉和变异算子.用该算法成功地求解出了三个著名的Muth-Thompson问题(MT6×6,MT10×10,MT20×5)的最优解.计算表明,该算法具有较高的效率,能有效地求解机器排序等复杂的组合优化问题.     

三目标单机随机调度问题

讨论一类具有随机加工时间的单机调度问题 ,目标是确定 n个独立工件的最优排序 ,使工件提前完工时间之和 ,延误时间之和及守工时间之和的线性组合之期望值最小 .在一定条件下得出最优排序的形状.     

基于模糊规则的GA求解成组调度

研究并行多机成组工件flow-time问题,利用模糊规则量化,使用遗传算法内嵌入模糊控制规划的智能化算法求解这类复杂的组合优化问题,最后给出计算实例及仿真结果,证明了该算法具有解决大规模实际问题的能力。     

一类有动态时间窗的并行多机启发式调度算法

航班过站服务中的货邮装卸作业调度是一类有时间窗和作业调整时间的多目标多设备并行作业动态排序问题，其特点是作业时间窗和服务作业时间动态变化。在分析区别于一般制造业生产作业排序特点的基础上，建立了服务作业的调度模型．提出了设备能力差的概念．给出一个考虑不同设备加工能力的启发式分配法。当时间窗或服务时间发生变化时，算法只需要修改判断矩阵中的一行或一列数据，而对算法运行的效率没有影响。算例分析显示，能力差分配算法在减少航班延误数量、时间压设备生产能力平衡上均优于目前使用的先到先服务和最小负荷调度的混合算法。     

软计算求解并行多机成组工件调度问题

自从Zade将模糊理论引入求解组合优化问题以来，出现了很多基于模糊规则与智能优化算法相结合的软计算方法，文章尝试将这种方法用于解决并行多机成组工件flow-time问题，本问题中，设有n个工件计划在M台并行一致的机器上加工，这n个工作根据相似性分为b组，开始加工时，需要一个准备时间，当工件接续在同组工件之后加工时，不需要准备时间，反之，接续在不同组工件之后加工时，需要一个准备时间，本问题的目标是找到一个工件加工的调度顺序序列，使M台机器总的流水时间最小，在文章中，作者首次利用模糊规则量化结合遗传算法的软计算方法求解这类复杂的组合优化问题，最后给出计算实例及仿真结果。     

混合Jobshop炼钢-连铸重调度方法及其应用

炼钢-连铸生产过程中加工设备起、停时间经常会出现严重延迟,导致调度计划不可行. 目前人工调整,存在响应速度慢和调整结果不优化的问题. 对炼钢-连铸混合Jobshop重调度问题进行了分析,提出了正在作业炉次已分配设备不变的重调度方法. 并提出了求解策略,将原调度分解为两个子调度问题. 引入炉次操作状态参数β,建立了正在作业炉次的时间修正模型,构造了启发式方法进行求解.对于未作业炉次,建立了多目标非线性0-1 整数规划模型,构造了并行逆推启发式算法进行设备指派,采用线性规划求解各操作的开工时间.基于上述方法开发了动态调度软件应用于国内某大型钢铁企业,在缩短动态调度时间、减少钢水冗余等待时间方面取得了显著成效.     

带公共交货期窗口的提前/拖期非等同多机调度问题

提出了公共交货期窗口下提前 /拖期惩罚的多台不同设备情形的零件排序模型 .在分析相应单机问题最优排序和最优交货期性质的基础上 ,证明该多机零件问题实际上蕴含着使系统 makespan达最小的多机零件排序问题 .由于使系统 makespan达最小的并行多机零件排序问题已被证明是 NP完全问题 ,因此提出了求解该零件排序问题的一个启发式算法 ,该算法计算复杂性低且对并行多机零件排序问题同样适用 .最后给出了两个数值例子 .     

An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies

This paper is concerned with the fractional version of online hierarchical scheduling problem on uniform machines. In the problem, the jobs and machines have several different hierarchies and each job can be arbitrarily split between the machines with hierarchies not above the hierarchy of the job. The objective is to minimize the makespan. The authors present an optimal algorithm for the problem with three hierarchies.     

多工件族无缓冲混合Flow Shop问题的模型和算法构建

旨在研究并解决一类从集装箱混合装卸作业环境中提取的多工件族无缓冲混合Flow Shop问题. 针对该问题的多工件族、无缓冲、部分专用机、与机器和顺序相关的准备时间和作业时间等特点, 构建了问题的混合整数线性规划模型. 鉴于问题的NP-hard特性, 构造型的启发式算法被构建, 核心思想是基于提出的机器库存和配额等概念, 动态构建含有三元副的调度列表, 三元副表示与其一一对应的工件在3阶混合Flow Shop中的加工轨迹. 通过仿真实验、下界分析, 发现算法能获得好的近优解和低的计算成本. 更为重要的是, 算法尤其适合解决大规模的实际问题.     

基于JIT的多目标并行多机调度问题的混合遗传算法

针对一类极小化 makespan和延迟区间的并行多机零件排序问题 ,设计了一个混合遗传算法 .该算法的特点是充分利用求解单机问题的最优有效算法 ,设计了一种简单的编码方案 ,简化了算法的实现难度 ,提高了算法的执行效率 .数值仿真实验表明 ,该算法具有收敛速度快、优化效果好等特点 ,且适合于求解大规模问题 .