一类加工需要额外资源的平行机调度问题的算法设计

给出了一类加工需要额外资源的平行机调度问题的精确算法。针对在平行机上加工的工件,除需要机器资源外,还需要一个单位额外资源的问题,考虑额外资源的种类和数量有限,以给出问题的最优调度使工件的完工时间最小为目标。该问题源于地球观测卫星的数据下载,在智能制造和信息处理等领域亦有广泛应用。给出了该问题的整数规划模型、最优解下界和分支定界算法;给出了一种有效的分支策略以避免重复分支,设计了相应的定界方法以提高算法的收敛速度。通过小规模实例和大量的数值仿真实验,验证了算法的正确性和在不同参数配置下的有效性。

考虑可拆分订单及加工类型匹配的平行机调度决策

介绍了制造资源共享环境下共享平台的生产和运作,以1688淘平台为例,将共享平台抽象刻画为考虑可拆分订单和加工类型匹配的平行机调度问题。客户将订单下达到共享平台上,供应商将闲置机器放在平台的资源池里。不同机器具有相同的加工速度但只能加工与其类型匹配的个性化订单,因此,需要决策使用哪些机器。一旦使用某台机器,会产生固定的加工或租赁成本。每个订单可以被拆分成整数长度的多个子订单,并在可用的机器上同时被加工。以最小化所使用机器的总加工成本和订单的总完工时间之和为优化目标,建立了一个整数线性规划模型。对于小规模实例,CPLEX可以求得最优解;对于中规模和大规模例子,提出了基于机器加工能力的贪婪算法和遗传算法。数据实验表明,基于机器加工能力的贪婪算法是一种高效且有效的算法。此外,尽量选择加工能力强的机器加工订单;将订单拆分在多台机器上并行加工可以缩短订单的完成时间。

机器带有周期维护和准备时间且工件可中断的混合平行机调度问题

从义齿加工厂隐形义齿和氧化锆全瓷牙这两种义齿的生产流程中,提炼出一类混合平行机生产调度问题。在这个问题中,一部分机器带有准备时间,剩余的机器将会设置对应的周期维护,在机器维护过程中不再进行工件加工,目标是最小化最大完工时间。在前人研究的基础上,对于机器只考虑准备时间或只考虑周期维护的特殊情况这2个问题提出了机器具有准备时间和周期维护的混合平行机调度问题,以注水模型为基础,结合每种机器的不同情况,通过分类讨论提出了两个多项式时间内可解的最优算法。

钻臂空间液压自动平行机构的平行机理

对钻臂空间液压自动平行机构的平行机理进行了理论分析论证。文中指出，只能对由前后变幅机构构成的二空间多面体相似时的初始位五实现无误差平行移动，对其它初始位置只能实现近似的平行移动。

基于禁忌搜索的平行机多工厂供应链调度

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

平行机及自由作业的排序与转包

研究工件排序与转包相联的模型,即制造商从客户处接受一批工件,这些工件既可以由制造商加工,也可以一定费用转包给承包商加工.制造商需要确定被转包的工件集及工件的加工顺序,使得加工费用和转包费用之和为最小.研究制造商为平行机及自由作业,承包商为单机情况下的排序与转包模型,基于动态规划算法给出了近似算法,并分析了该算法的性能比.

考虑外包的平行机调度问题的多目标遗传算法

研究了一类考虑外包的平行机调度问题,目标是使作业外包总成本与最大完工时间同时最小化。通过对该类问题进行形式化描述与分析,设计了一种数字串形式的解的表示方法,其中每位数字表示固定作业对应的机器编号,该方法能够有效缩小解空间,从而提高搜索效率。进而构建了一种带精英策略的非支配遗传算法PD-NSGA-Ⅱ,为该类多目标调度问题提供Pareto最优解集。大量数据实验结果表明,所构造的PD-NSGA-Ⅱ算法能够在合理的时间内有效求解该类调度问题,其解的质量与计算效率均优于SPEA算法。

具有学习效应的平行机排序问题

针对具有学习效应的平行机排序模型,讨论了两类问题。在这一模型中,工件的实际加工时间不仅与其所在排序中的位置有关并且与其本身的学习率有关,对于在同一台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。第1类问题的目标函数是极小化提前与延误的加权和;第2类问题的目标函数是极小化提前与误工工件数的加权和。对这两类问题分别给出了多项式算法。

平行机供应链排序及转包多目标模型

研究一类允许订单转包的供应链排序问题,即供应链由一个制造商、多个承包商和一个客户组成,制造商从客户处接受一批订单,这些订单既可以由制造商完成生产和分批配送,也可以转包给承包商完成.制造商需要确定被转包的订单集并安排订单的生产和运输,使得完成所有订单的最长提前期与制造商的总成本这两个目标的加权和最小.针对制造商为平行机生产环境、承包商为单机生产环境的情况,分析了问题的复杂性,构建了问题的非线性混合整数规划模型,并给出了模型的求解方法.最后,仿真实验结果表明了模型和求解方法是合理的和有效的.

最小化时间表长的平行机调度近似算法研究

讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.

具有凸资源消耗函数的最小化Makespan的平行机调度问题

研究了一类资源受限的平行机调度问题,其中假定作业的处理时间是其消耗资源量的凸减函数,调度的目标是在限定资源总量的情况下最小化Makespan(最大完工时间)。给出了此类NP-hard问题的形式化描述。定义了关键机器与非关键机器,给出了非最优解必定存在非关键机器的论断。尽快缩短非关键机器与关键机器之间工作量的差距能够有效逼近最优解,从而构造了快速的模拟退火算法。设计了一个下界用于衡量解的精度,并用于构造模拟退火算法迭代结束条件。算法性能通过20000组随机数值算例进行了测试,实验结果表明所构造的模拟退火算法能够在0.1秒之内有效求解1000个作业的问题并将相对误差控制在0.01%以内。该算法体现出很高的精度和计算效率。

带并行工件的平行机排序问题的一个新近似算法

讨论并行工件平行机排序问题,目标为极小化所有工件的总完工时间.这是一个强NP-难的问题.通过对(0,1]区间划分的深入研究,提出了一个多项式时间的近似算法,其渐近性能比的上界为1.6,下界为1.5.该算法比LI(1999)中提出的算法的渐近性能比明显地小.

有两个服务等级的平行机排序问题

对有两个服务等级的平行机排序问题的m台机情形,证明了修正的MF算法的最坏情况界不超过4/3＋（1/2）^k,其中k是算法中预先给定的迭代次数.而已有的算法仅为2-1/m-1,从而大大改进了已有文献中的结果.

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

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

可拆分平行机排序问题研究

平行机排序问题是把n个产品安排到m台机器上加工，使其总费用最小．通常的平行机排序问题都假设（C1）：任何产品不能在不同机器上同时加工．但是，如果把产品的加工时间看成一个产品量的需求，就可以假设（C2）：允许同一产品拆分在不同机器上同时加工．本文首先回顾了C1假设下平行机排序问题已有的结果，然后基于假设C2，讨论了各种费用目标下问题的算法及其复杂性．在没有生产准备时间的情况下，给出了一些问题的多项式算法和线性规划方法．在有独立生产准备时间的情况下，给出了P／split／Cmax问题的启发式算法及其算法分析．

带约束的平行机排序问题

讨论了带资源约束和机器准备时间的平行机排序问题 ,资源约束是指每个机器最多加工k个工件 .首先对一般情况下的同型机的PLPT排序进行了讨论 ;并首次对同类机排序进行了研究 ,给出了一个FLPT近似算法 ,同时对m =2时证明了PLPT排序的最坏情况紧界是 2 .

可拆分平行机排序问题的一个启发式算法

为缩短工件的完工时间,将极小化最大完工时间的平行机排序问题作为研究目标。在此问题中,允许同一工件拆分成多个子工件在不同的机器上同时加工,同一工件的任何2个子工件不可在同一台机器上加工。与以往研究不同,对工件的拆分方式进行了限制,即工件拆分后所得子工件的长度不能小于给定的阀值,且工件拆分次数尽量少,这是一个NP难问题。借助于LPT算法的思想,提出了一个求解该问题的启发式算法,实现了工件的自动拆分和工件到机器上的自动分配。通过多个实例对文中算法进行了测试,数值结果表明:该算法可行、稳定性良好,适用于工件拆分方式具有类似限制的平行机排序问题的方案决策。

平行机作业环境下的订单分配与排序

针对一类平行机作业环境下的订单分配与排序问题,从整体的角度协同优化供应链中的订单分配、生产调度和分批运输调度。以完成所有订单的总订货提前期与生产运输总成本的加权和最小化为目标,构建了问题的数学模型。将基于向量组编码结构的禁忌搜索算法与基于动态规划方法的启发式算法相结合,设计了一种混合优化算法以求解问题。对不同策略和不同算法进行比较,数据实验结果显示了订单分配与排序策略的优越性及所提算法的有效性。

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.

基于增强学习的平行机调度研究

尝试运用增强学习方法来研究平行机调度问题,通过定义系统状态、行为和报酬函数,把调度问题转化为平均报酬型半马尔可夫决策过程,并使用结合函数泛化器的R-Learning算法来解决。提出排名算法,并利用它和两种常用的调度规则(最短期望加工时间规则和先进先出规则)来定义增强学习的行为。实验结果表明,R-Learning算法通过仿真实验学习较优的调度策略,在不同的决策状态下选择最优或次优的行为,对每个测试问题的效果都优于以上任何一条调度规则。