考虑恶化和学习效应的单机成组排序问题

讨论了工件加工时间同时具有恶化和学习效应的单机成组排序问题。在这类问题中,同一组中的工件不允许分开加工,各组之间有安装时间,其中安装时间是工件组开始加工时间的简单线性函数,各组内工件的实际加工时间是关于恶化和学习效应的函数。对目标函数为最大完工时间和总完工时间两类问题分别给出了多项式时间最优算法。     

一类安装时间受资源约束的单机成组排序问题

讨论了具有连续资源的单机成组排序问题。在这类问题中,同一组内的工件不允许分开加工,各工件组的安装时间是所消耗资源的线性非增连续函数,同一组内的工件具有同位置有关的学习效应。考虑三类问题,第一类问题的目标函数是在满足最大完工时间限制条件下,极小化资源消耗总量;第二类问题是在满足资源消耗总量限制条件下,极小化最大完工时间;第三类问题是在满足资源消耗总量限制条件下,极小化最大完工时间与资源加权消耗总量的加权线性组合。对三类问题分别给出了求解最优资源分配的方法,并通过数值例子进行了说明。     

树约束线性加工时间的单机排序问题

讨论工件具有线性加工时间,工件间优先约束为树约束的单机排序问题。当目标函数为极小化加权完工时间和时,问题比相应的经典排序问题复杂,在工件间优先约束为出、入树2种情况下,分别给出了该问题最优排序的多项式算法。     

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

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

加工时间带恶化和指数学习效应的成组排序

本文研究了成组技术下带依靠时间的线性恶化效应和依靠位置的指数学习效应的排序问题.模型中,组安装时间是开始安装时间的线性函数,工件的加工时间带线性恶化和指数学习效应,对最小化时间表长问题和最小化总完工时间问题分别给出了多项式算法.     

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

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

链约束线性加工时间单机排序问题

讨论工件具有线性加工时间,工件间具有链约束的单机排序问题。目标函数为极小化加权完工时间和。在这类问题中,工件的加工时间是其开工时间的线性函数。对链不允许中断和链允许中断两种情况分别给出了最优算法。     

带有学习效应和机器可用性限制的排序问题

针对单机和两台机器的平行机排序问题,建立了机器具有学习效应和可用性限制的排序模型。在这个模型中,机器具有学习效应。在学习效应下,工件的加工时间与所排位置有关,对于需要在同台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。同时由于定期维修等原因而导致机器在某段时间内不能加工工件。考虑了目标函数为极小化总完工时间的单机和两台机器的平行机问题。对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法。     

线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题。在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数。考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量。第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间。对两类问题讨论了最优排序的某些特征。基于对问题的分析,分别给出了求解最优资源分配的方法。结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立。     

交货期固定的工件准时完工数——最大排序问题的多项式时间算法

给出了求解交货期固定的工件准时完工数最大的排序问题的多项式时间算法。     

交货期服从指数分布的单机随机调度问题

工件完成时间与交货期差的绝对值加权和最小化单机随机调度问题是JIT（just-in-time)生产环境下的典型调度模型，是NP－hard问题，然而，当工件权值与加工时间成正比时，LPT（largest processing time）工件调度是问题的最优解，讨论了该问题加工时间和交货期都为随机变量，其中交货期服从指数分布，且工件权值与加工时间成正比的情形，给出了问题的最优解，并在一定条件下将结果推广到机器随机故障的情形。     

模糊加工时间调度问题的研究

提出模糊加工时间调度问题,隶属函数建立在工件的模糊加工时间上,隶属度表示工件在一段加工时间下属于完工集合的程度,在假设工件的隶属函数是单调递增的情况下,的多个工件所迭加的联合隶属函数所对应的性质,根据迪些性质研究了一种单机模糊加工时间的调度模型。     

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究3台机器调整时间可分离的无等待F1ow Shop排序问题，目标函数为极小化折扣加权总完工时间。对某些特殊情况，给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待F1ow Shop排序问题的分派规则。     

AN IMPROVED BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE WEIGHTED FLOWTIME ON IDENTICAL PARALLEL MACHINES WITH FAMILY SETUP TIMES

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.     

平顺移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度

对平行顺序移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度问题展开研究.构建以加工制造设备总停机次数、批量工件生产周期以及搬运批量工件的总次数为决策目标的基于分层序列法的多目标决策模型,利用该模型可确定批量工件的最优加工排序方案.建立平行顺序移动模式的加工与调整时间模型,该模型是求解生产周期的基础,也是为批量工件的最优调度方案制定生产作业计划的依据.提出并设计平行顺序移动模式下考虑加工时间与调整时间可分离的禁忌搜索算法对问题进行求解.研究结果表明:本研究可为平顺移动模式下考虑加工时间与调整时间可分离的批量生产流水车间选出批量工件的最优调度方案,同时可为批量工件的加工和加工制造设备的调整制定精确的生产作业计划.     

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

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

带运输和设置时间的无等待并行流水车间调度问题研究

研究了一类从无缝钢管生产作业中提炼出的新的并行流水车间调度问题.该问题具有工件无等待、工序之间存在运输时间、设备需要调整时间等特点.这些特点使得问题变得相当复杂.建立了大规模的混合整数规划模型,通过提出的变换方法简化和降低了模型的规模.针对此模型,提出并开发了适合此问题的遗传算法.通过实验比较六种规则调度方法及遗传算法的性能.计算结果表明,六种规则调度中最好的方法是SPT,而遗传算法调度的性能优于SPT.     

求解多目标作业排序问题的遗传算法

利用联合进化遗传算法 ( CEGA)建立了求解多目标排序问题的一般框架 ,采用目标权衡分析诱导出决策人的偏好关系 ,并将其引入求解过程 ,以确定满意排序 ,在搜索寻优过程中 ,将启发式与遗传算法相结合 ,以提高搜索效率 .最后 ,利用该算法框架求解了一个含调整时间的一般 Job Shop排序问题 ,以表明算法的有效性.