公共交货期窗口的单机随机调度问题

讨论一类具有随机加工时间的单机调度问题,所有工件设置一个公共交货期窗口,每个工件的加工时间服从正态分布,目标是确定n个独立工件的一个排序,使工件的提前／延期之和与完工时间之和的线性组合之期望值最小。问题的最优解具有v-型特征。     

加工时间服从指数分布单机随机调度

讨论加工时间服从指数分布的单机随机调度问题，目标是实现工件完成时间与公共交货期偏差的加权和期望最小化。此问题是JIT（Just-In-Time)生产环境下的典型调度模型。结果表明问题的最优解关于权值与加工时间均值的商具有∧形特征。     

一类单机随机调度问题解的特征

讨论了加工时间随机的单机调度问题，工件的加工时间服从指数分布，目标函数具有一般形式，涉及工件完成时间与交货期偏差的正规和非正规目标函数，如工件关于交货期拖后时间期望和，工件完成时间关于交货期绝对偏差的期望和等，都是其特殊情形．给出了最优解的特征，包括SEPT(shortest expected pro—cessing time)调度，LEPT(largest expected processing time)调度和关于加工时间参数的A形调度,这些特征可用于确定问题的最优解。     

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

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

单机随机调度最优解的Λ形特征

讨论具有随机加工时间的单机调度问题,目的是确定ｎ个工件的一个排序使得完成时间与一公共交货期差的绝对值加权和的期望最小．在假定加工时间和交货期都服从负指数分布时,建立了此随机调度问题等价的确定形式,并讨论了最优解的Λ形特征．然后,在一定条件下将上述结果推广到机器随机故障的情形．     

单机随机调度最优解的∧形特征

讨论具有随机加工时间的单机调度问题,目的是确定n个工件的一个排序使得完成时间与一公共交货期差的绝对值加权和的期望最小,在假定加工时间和交货期都服从负指数分布时,建立了此随机调度问题等价的确定形式,并讨论了最优解的∧形特征,然后,在一定条件下将上述结果推广到机器随机故障的情形。     

带不可用时间段的单机调度问题的启发式算法

研究了机器带有一个不可用时间段的部分可续型单机最大完工时间调度问题,提出了一种启发式算法,证明了其相对误差界,并举例说明该界是紧的,而且据此推出了该算法对相应不可续问题的相对误差界,此界低于该问题现有算法的界.将此算法与其它算法进行了多方面的比较,包括利用随机数据进行实验以评估其相对误差,结果表明此算法是一种非常高效的启发式算法.     

随机机器故障下单机预测调度方法

研究可能遭遇机器故障的工件动态到达的单机总加权拖期生产调度问题. 基于一定概率分布对机器故障的预测描述, 预测调度方法可以用插入时间冗余的方法使初始调度方案具有一定的抗干扰能力, 对未来的故障扰动有一定预测性, 使未来实现调度与预测调度尽量保持一致性, 预测性度量定义为实现调度与预测调度间各工件完工时间的绝对偏离加权和. 提出了一种带空闲时间阈值的预测调度方法, 基于工件动态到达的特点, 充分利用初始调度中的空闲时间, 通过空闲时间阈值灵活控制空闲时间的插入与否. 大量的仿真实验结果表明,与已有方法相比, 采用该方法得到的预测调度对随机机器故障的预测能力更高,同时保持了好的调度性能.     

链优先约束工件单机随机排序问题

讨论单机随机排序问题，目标函数为确定工件的排列顺序使工件的加权完工时间和的数学期望最小。设工件问具有平行链优先约束，机器发生随机故障。考虑两种情况，第一种情况是链不允许中断．第二种情况是链允许中断，对两种情况分别给出最优算法。     

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

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

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

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

单机不同尺寸工件批调度问题的优化算法

研究了单机环境下不同尺寸工件的批调度问题,引入微粒群算法对制造跨度进行优化.首先给出了问题的微粒表达形式,并根据问题的离散优化特性对微粒状态的更新方法进行了改进;然后将微粒群算法和分批的启发式算法进行有效结合,改善近似解的质量.实验中对各类不同规模的算例均进行了仿真,结果表明了微粒群算法的有效性.     

改进蚁群算法求解单机总加权延迟调度问题

单机总加权延迟调度(SMTWTS)问题是一类由于任务完工时间超过交货期从而优化目标为加权延迟成本最小的单机调度问题,已被证明是NP难题.蚁群算法受自然界蚁群觅食机理启发而来,也曾被用于其它类型的单机调度问题研究,但SMTWTS被认为是实际生产中面临的主要问题.本文提出一种改进蚁群算法求解SMTWTS问题,该算法对信息素更新策略进行了改进,引入信息扰动及变异策略,并对参数进行了合理设置,对比实验表明搜索效率好于遗传算法.     

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

研究工件具有线性加工时间、工件间优先约束为树约束的单机排序问题。目标函数为极小化加权完工时间和。在工件加工时间是其开工时间的线性函数的条件下，本文证明了最大家庭树中的工件优先于家庭树中的其它工件的加工，并且其工件连续加工所得到的排序为最优排序。     

一个批处理机随机调度模型

以零售业企业（超市、百货商店、仓储式商场等）进货为背景新建立一个批处理机随机调度模型．模型中含两个问题，首先分别将它们转化成了与其等价的确定优化问题，接着给出了确定优化问题的最优调度的性质，最后基于性质给出了求解确定优化问题的算法。     

加工能力受扰的可控排序干扰管理

在加工时间可控的单机排序中,面对随机发生的干扰事件,研究了初始加工时间表的制定问题。对于干扰事件造成的影响采用匹配时间排序的应对策略,在干扰事件发生后,通过压缩工件加工时间,使新时间表在某时间点后完全恢复到初始加工时间表。基于工件吸收干扰事件影响的能力,设计复合排序规则来决定工件的优先级。由于问题内在的复杂性,在复合排序规则中,应用遗传算法来确定某给定待处理工件集的最优参数。使用概率分布表示干扰事件的发生时刻和持续时间,并综合概率信息和工件的优先级来制定初始加工时间表。最后,通过随机数值试验模拟,发现本文设计的初始时间表优于根据最短加工时间优先规则制定的初始时间表,验证了方法对于处理干扰事件影响的有效性。