供应链排序中的外包问题 (运筹学与控制论)

为了更好地将供应链排序和现实生活结合以体现其应用价值,文章研究了一类可以外包的供应链排序模型。外包即指为了提升效率,节省总费用,而采取将工件由其它制造商代替加工的现象。所有的工件均可以在制造商内部加工也可以进行外包加工,外包工件加工完成后必须分批运回制造商才算完工。所研究的模型中有一个制造商和一个外包商,制造商的加工环境为m台平行机,外包商为单台机器。因此在模型中要考虑外包费用、运输延迟以及运输费用,所要做的就是确定外包工件以及工件的加工顺序和外包工件的配送顺序。对于该问题,本文主要研究了目标函数分别为总完工时间、最大延迟以及误工总数的情形;分析了问题的复杂性,运用动态规划的技巧给出了最优算法且分析了算法的时间复杂性。     

工件可外包的单机准时排序问题

【目的】研究一类单机准时排序问题,其中工件有公共的交货期和交货截止期,允许工件外包加工,外包加工将产生外包费用,目标是极小化总提前时间,总延迟时间与总外包费用之和。【方法】首先给出该问题的若干最优性性质,然后对于交货期和交货截止期都待定,以及给定交货截止期两种情形分别讨论。【结果】对于第一种情形,设计了多项式时间算法,对于第二种情形,证明了它是NP-困难的并设计了伪多项式时间的动态规划算法。【结论】所讨论的单机准时排序问题所得到的结果为冷鲜食品生产管理者提供了有效决策支持。     

供应链排序问题

所考虑的供应链排序系统为：若干个不同的元件供应商向一产品加工商供应产品元件,产品加工商等所有的元件都加工完成后再开始最后阶段的加工即成品加工;假定成品完工时间是所有元件中最后完工的元件的完工时间（即成品加工是无瓶颈的且将工时设为零）;目标函数是极小化工件所有元件的带权的完工时间之和。对于问题As ｜｜s∑i=1 n∑j=1WijCij.设计出了它的一个计算时间为（n^2logn）的多项式时间算法．     

基于多属性决策的供应链排序问题研究

文章以生产排序费用和分批发送费用总和最小为排序目标,考虑包含单个供应商向多制造商供应工件的供应链排序问题,并建立了问题的数学模型;提出了一种融合多属性决策方法的动态规划算法,给出了相应算例,并分析了算法的复杂度。     

带有安装时间以及可分批加工的供应链排序问题

研究了单制造商多客户的供应链排序问题;同一客户的工件可以分批进行加工,不同客户的工件不可以在一批中加工;当相邻的两批工件属于不同客户时则需要相应的安装时间.以生产和运输总费用最小为目标函数,建立了集成排序模型;分别用工件的加权总完工时间和最大延迟作为排序目标,采用动态规划的技巧给出了最优算法,并分析算法复杂性.     

工件的排序生产和运输问题

该文研究平行机环境下的供应链排序，使生产排序费用和发送费用总和最少．生产排序费用用工件的完工函数表示，发送费用只考虑固定费用．在研究最优解性质的的前提下，给出相应的动态规划算法，并分析算法的复杂性，给出算例．     

三台平行机上四个约束链的排序问题

考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.     

基于患者门诊就医的双任务排序问题

【目的】为解决门诊患者在同一位医生处初次就诊、检查(检验)后确诊两个阶段的优化安排,使门诊患者尽早完成就医诊疗。【方法】将患者门诊就医的问题转化为一个双任务排序问题,建立问题的数学模型,提出一个动态规划算法。【结果】对于这个双任务排序问题,当第一个任务的加工时间与两任务的时间间隔为常数时,此动态规划算法为多项式时间的最优算法。【结论】对于改善医院门诊的叫号系统,提高就医效率提供了重要的研究方法。     

带有准备时间的可拒绝供应链排序

考虑可拒绝排序中生产与配送的集成问题.有一个制造商和多个客户,不同的客户订购不同种类的工件.机器在加工不同种类的工件前要有一个准备时间.对于客户的工件制造商可以选择接受或拒绝加工,但当工件被拒绝时制造商需要支付相应的拒绝费用.每个工件有自己的工期并且生产完成后需要配送到相应的客户处,每一批配送需要花费一定的时间和费用.该文研究了排序理论中几个主要的目标函数,给出了相应的动态规划算法并分析了算法的复杂性.     

供应链管理中的一类分批调度问题

研究了一类集成配送和加工的供应链调度问题.在配送阶段,由多辆运输工具将工件从仓储区运送到批处理机进行深加工;在加工阶段,工件在批处理机上成批加工,批加工费用固定.目标函数是极小化最大完工时间和总加工费用之和.证明了该问题是NP-难的,并对该问题的一类特殊情形给出了多项式时间算法.     

基于无等待约束的供应链在线调度问题

研究了供应链在线调度问题.给出了在不改变已有工件调度的情况下,最早完成临时订单的算法,该算法在寻优过程中结合了微粒群算法的局部搜索能力,计算机仿真结果表明,在大规模订单的情况下,该算法同样能很快找到最优加工方案.     

带有释放时间的半连续型批处理机调度问题(运筹学与控制论)

半连续批处理机调度问题,是从钢铁工业加热炉对管坯的加热过程中提炼出来的。工件按批加工,同一批中工件的加工时间等于此批中工件的最大加工时间,且工件必须按周期一个紧挨着一个进入、离开处理机。批处理机的容量为C,即最多可同时加工C个工件,批的容量为批中工件的个数,批的处理时间与批中工件的加工时间、批处理的容量和批的容量有关。本文研究释放时间与加工时间一致时,对于目标函数为最大完工时间问题,即时间表长问题,分析其最优解的性质,从而将问题转化为工件按释放时间非减顺序排列后,对工件进行分批,使得最大完工时间最小。在此基础上给出了一个复杂性为O(n2)的动态规划算法,证明了这个算法的最优性,并用数值例子进一步说明了算法的计算过程。     

出厂物流调度问题及其启发式算法

针对出厂物流调度问题,建立了一类出厂物流问题的调度理论模型,证明了该问题的强NP-hard特性.基于对问题的特征分析,提出求解问题的近似算法,证明了算法的最坏性能比为3且为紧界,并通过数值仿真验证了该算法的有效性.结果表明,所提出算法对两台流水作业机器的完工时间有一定的优化.     

复杂供应链网络资源传输数据自动调度方法

为了解决传统方法实时性较差、公平性极低、容易造成复杂供应链网络崩溃,以及无法有效调度拥塞情况下数据,导致调度性能下降的问题。研究了一种新的复杂供应链网络资源传输数据自动调度方法。分析了传输数据过程中出现数据包乱序现象的原因,发现在复杂供应链网络出现拥塞的情况下,拥塞部分和网络路由部分会出现很大的改变。针对拥塞部分进行调度时,对数据传输过程中拥塞状态下数据调度问题进行描述。结合公平性考虑,通过粒子群算法进行求解。针对路由部分进行调度时,考虑带宽预测与前向传输时延。对各子路径接收端成功接收数据包数量进行预测,依据子路径往返时延,完成对子路径的排序,按照顺序调度数据传输。在出现丢包情况时,通过最大ssthresh优先法对丢包重传路径进行选择。结果表明:所提方法可动态自适应调度不同路径的传输数据,分配比率相对稳定;接收缓存空闲空间变化较少,乱序数据包数量明显降低,拥塞窗口数量最低;公平性因子值明显低于其他方法。可见所提方法调度性能优,可达到复杂供应链网络资源传输数据调度要求。     

工件相同且发送批数受限的供应链排序问题

工件完工后成批发送的供应链排序问题是从实际生产中提炼出来的,针对发送批数受限制,最小化生产费用及发送费用的情况,当工件的权重与加工时间均相等时,生产费用是关于发送批数的单调递减函数,进而根据二分搜索法可以得到最优的发送批数。因此问题是多项式时间可解的。     

具有能力约束的供应链系统模型

针对包含一个供应商、一个制造商和一个经销商的三级供应链系统进行研究,并依次将系统中的成员称之为首级、中间级和尾级.在相关文献研究的首级和尾级具有能力约束的供应链系统联合批量模型的基础上,建立了一个中间级具有能力约束的三级供应链系统的联合批量模型,并提出了基于推拉混合规则的新的动态规划算法,可在多项式时间求解供应链系统中各个层级的最优决策批量,并通过相关定理的证明保证了算法能够求得全局最优解.最后通过算例分析对上述方法进行了阐述.     

平行机上一种带拒绝费用的排序问题研究

主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP一难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。     

一种特殊的单机双目标分批排序问题

考虑目标函数为Cmax和∑ωjCj的单机上批容量无限制的两类双目标分批排序模型:约束模型和线性加权模型.这里通过动态规划的递推算法分别给出了相应问题的多项式时间算法,并分析了算法的时间复杂性.最后指出在本文约束模型解决前提之下.问题相应的主次指标模型也可相应解决.