摘要：研究制造商具有若干台平行机且允许工件转包给仅有一台单机的承包商加工排序问题.工件转包需要一定的转包费用以及运输时间.研究确定要转包工件集以及所有工件的加工顺序,分别为极小化工件总完工时间,最大延误,误工工件数与转包费用之和,证明了问题的NP困难性,并分别设计动态规划算法.

摘要：以绿色制造为背景,假定机器设备具有不同的能源消耗成本或维护成本,研究了一类考虑成本限制的平行机调度问题.调度的目标是最小化最大延迟时间.为该问题建立了整数规划模型MIP,设计了改进的EDD (earliest due date firstly)算法,命名为MEDD.由于考虑成本限制,证明了MEDD算法的可行性,并进而理论分析了算法的最坏误差界.通过算例说明了算法的执行情况,同时采用大量随机数据实验验证算法的性能.对于小规模问题,将MEDD的解与MIP的精确解进行了对比;对于大规模问题,由于MIP精确解难以获得,以MIP对应的线性规划松弛模型MLP的最优值为下界对MEDD算法的解进行了衡量.实验结果表明了所构建MEDD算法的有效性.

摘要：在考虑能耗的平行机调度问题中同时考虑设备可靠性对能耗成本的影响,以最小化延迟成本和能耗成本加权和为调度目标,建立数学规划模型.设计了蚁群算法对问题进行求解,引入一种新的启发因子定义蚁群搜索过程,并通过局部搜索算法提升蚁群搜索的质量.算例实验结果表明该调度方法有效且具有较高的效率,可以降低能耗及生产总成本,具有实用价值.通过敏感性分析研究了设备可靠性离散程度、交付期松紧对于调度决策的影响,可为车间实际生产决策提供支持.

摘要：针对工件加工需要额外资源且额外资源有两个单位可用的平行机调度问题,目标是极小化最大完工时间,给出了一个近似算法。首先,说明了该问题是NP-难的,并给出了该问题的整数规划模型和最优解的下界;然后,设计了该问题的一个近似算法,通过分析算法的性质,证明了该算法的最坏情况界不大于3-2/m;最后,通过大量的数值实验验证算法在平均情况下的性能。数值实验结果表明,该算法在工件数、额外资源数和机器数等因素扰动下都体现了较好的性能。该算法可为需要额外资源调度问题的高效算法设计提供参考。

摘要：研究一类考虑转包的供应链排序问题,即工厂从客户处接受一批订单,这些订单既可以由工厂完成,也可以通过支付一定费用进行转包.工厂需要确定被转包的订单集并安排未被转包订单的生产和运输.针对工厂为平行机生产环境的情况,以交货期限内完成所有订单的转包成本、生产成本与运输成本之和最小化为目标,构建了问题的数学模型,并设计了启发式算法.最后通过数值实验结果表明了算法的有效性.

摘要：提出一类平行机多工厂供应链调度问题,从整体的角度优化订单分配、生产调度和运输调度。以交货期限内完成所有工件的生产和运输总成本最小化为目标,构建了问题的混合整数规划模型。设计了一种基于向量组编码结构的禁忌搜索算法以求解该问题。使用供应链调度策略和独立决策策略分别对算例进行求解,数据结果验证了供应链调度策略的优越性。禁忌搜索算法结果与CPLEX的求解结果对比表明,禁忌搜索算法有效可行。

摘要：研究了将服务等级与拒绝费用2种模型复合起来的平行机排序问题.设有2台平行机M_1,M_2,加工速度相同;n个工件J_1,J_2,…,J_n分别按列表在线到达,每个工件J_j含有3个参数:加工长度t_j、拒绝费用p_j以及服务等级g_j=1,2.当工件到达时,可以接收加工,占用一定的加工时间;亦可拒绝,付出相应的罚值.目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.进一步,当且仅当g(M_i)≤g_j时,工件J_j可以分配给机器Mi加工,即机器M_1可以加工所有工件,机器M_2只能加工等级为g_j=2的工件,允许中断加工.设计了在线算法PH,并证明其竞争比为1+2^(1/2)/2≈1.707,下界为1.618,上下界差约为0.089.

摘要：本文考虑一类新的在线平行机排序模型一实时到达在线问题．该模型中，工件是陆续到达的．工件的个数及到达时间是事先未知的，而且只有当工件到达，才知其加工时间，所求目标是使所有工件都加工完的时间达到最小．对两台平行机的情形，Ｃｈｅｎ与Ｖｅｓｔｊｅｎｓ［２］给出了近似比为３／２的在线ＬＰＴ算法，并证明不存在近似比小于（５－）／２的算法．我们利用黄金分割数设计了一个新的算法，其近似比不超过（１８－５）／１１．

摘要：将差异工件的批调度问题扩展到两客户生产环境,建立了两个客户分别以最小化制造时间跨度和最小化最大工件延迟时间为生产目标的差异工件平行机批调度模型.首先提出了一种启发式算法TSEDD(two-set earliest due date)对分批方案进行排序并安排到平行机,然后设计了一个多目标蚁群优化算法MOACO(multi-objective ant colony optimization)对不同客户中的工件进行分批并结合TSEDD完成对问题Pareto最优解集的求解.实验结果表明,与经典的多目标问题求解算法NSGA-Ⅱ和SPEA2算法相比,MOACO具有较好的求解效果,且随着问题中工件规模的增大,算法的优势更加明显.

摘要：针对考虑机器适用性的相同工件平行机调度问题,提出1种二阶段近似调度算法。算法建立了问题的半匹配模型G=[J∪M,E,W],将原问题转化为最优半匹配搜索问题,然后通过初始解构造和优化得到问题的近似解。通过分析G=[J∪M,E,W]的拓扑统计信息对机器均载的影响,设计了初始解构造启发式规则。在此基础上,采用贪心原理,提出了基于启发式规则的初始解构造算法。初始解优化算法以初始解为起点,采用基于交错路径的局部优化方法得到近似解。通过交错路径树,搜索最优交错路径是影响初始解优化算法的重要因素。为提高搜索效率,限定交错路径的最大长度为4。最后,从理论上分析了算法的最坏情况界和时间复杂度。