关于机器排序虚图问题

1 问题的提出及模型设有 N 个工件要在 M 台机器上加工,按工艺技术的要求或规定,某个工件必须在特定的机器上加工,每个工件在某个机器上加工所需时间是一定的,每个工件由于规格要求不同,它在各台机器上加工的顺序也不同,并且也可能仅在 M 台机器中的一部分机器上     

具有学习效应且交货期可指派的单机排序问题

探讨了工件具有CON/SLK交货期指派且机器具有与位置有关的学习效应目标为极小化交货期指派费用、无误工工件的提前费用以及误工工件的惩罚费用之和排序问题.所探讨的问题在无误工工件数确定的情况下可以转化为指派问题,由于误工工件数最多有n种可能且指派问题能在O(n3)时间内解决,故排序问题是多项式时间可解的,并给出最优算法;在恶化工件具有CON/SLK交货期指派的基础上同时考虑了机器具有学习效应的排序,并给出了两种问题的多项式时间最优算法.     

工件可选择的平行机在线排序

研究了一类平行机在线排序问题,且工件可以选择.用三参数法表示该模型为:Pm|on-line,rj,D|∑,fJ.其中D指机器使用期限,fj为工件Jj的加工利润,目标函数是使得在机器使用期限内所获总利润最大.本文给出了该模型fj=1情形(即工件费用相同)的所有在线g法竞争比的上界1/2,进而给出了两台机器、fj=1且工件序列只含两类工件情形(小工件加工时间为1,大工件加工时间为d≥2)的在线算法(ξ)1,其竞争比为1/2,为最具竞争性的     

两个带机器准备时间的半在线排序

研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时间的同型机上加工的半在线排序,证明了其竞争比为2/3.     

一种改进的排序问题

本文研究的排序问题:有两族同型机,工件在每族机器上各有一个加工时间,考虑的目标函数是在模型中极小化两族机器上最大完工时间的最大者.     

带有路径和运输方式选择的供应链排序算法研究

主要研究了在供应链中具有单台机器的单个制造商、多个客户的生产和运输的集成排序问题.以生产排序和运输的总费用达到最小作为目标函数.其中生产排序费用是用工件送达时间的函数表示,发送费用是由固定费用和可变费用组成,可变费用与路径和运输方式的选择有关.对该问题的两类特殊情形给出了基于动态规划的多项式时间算法.     

预防性周期维护下考虑可中断工件的再制造单机调度(英文)

研究预防性周期维护策略下再制造系统中可中断和不可中断2类工件的单机调度问题.以最小化完工时间为目标,提出了LPT-LS算法,该算法首先按LPT(longest processing time)规则安排不可中断工件,然后按LS(list scheduling)规则安排可中断工件.并根据可中断工件的总加工时间(记为S2)分3种情况证明了该算法的最坏情况比,结论如下:当S2大于按LPT规则安排不可中断工件后机器的空闲时间时,最坏情况比为1;当S2介于分别按LPT规则和OPT(最优排序)规则安排不可中断工件后机器的空闲时间之间时,最坏情况比小于2;当S2小于按OPT规则安排不可中断工件后机器的空闲时间时,最坏情况比小于2.最后通过算例验证了结论的正确性.     

带学习效应的供应链排序算法研究

考虑了机器在加工工件时会具有学习效应这一实际条件,将具有单制造商的供应链排序推广到具有多制造商的供应链排序问题.以总的加权配送时间和配送费用达到最小作为目标,在分析解的最优性条件的基础上,分别给出问题在工件具有一致性权重和不分批配送假设下的最优算法,并分析算法的时间复杂性.最后给出该问题的近似值.     

两台同类机极小化总完工时间的分批排序问题

考虑了两台同类机极小化总完工时间的分批排序问题,给出了计算复杂性为O(n3)的动态规划算法,并将此算法推广到了工件具有学习效应的情况.     

工件带拒绝费用的单机排序问题

在经典排序模型中,我们往往假定机器必须加工所有的工件,并且它们的加工时间都是给定的。但是在许多现实的应用中,若某个工件的加工时间或者加工费用很大,我们就会考虑是否要加工该工件,我们既可以选择付出一定的费用而拒绝加工该工件也可以选择不付费而加工它。这时目标函数不再是传统的最大总完工时间,极小化最大完工时间,最大延迟等,而是要同时考虑费用,我们把这种排序称为可拒绝排序[1][2]。本文研究了工件带拒绝费用的单机分族分批排序问题。主要证明了问题1,sfg|family-jobs,rej|Cmax+∑j∈sej和1,sfg|family-jobs,rej,b|Cmax+jisej是NP-难的,给出了它们的近似算法。     

加工时间依赖工件位置的树约束单机排序问题

讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序.     

带磨损因子的排序问题

本考虑下述带磨损因子的排序问题：n个工件j，j=1，2，…，n，在同一台机器上依次加工，其所需的加工时间同它被开始加工的时间有关，越后加工其所需的加工时间越多；要求适当排列这n个工件的加工顺序，使目标函数值达最小．对加工全程、完工时间之和这两个目标函数中给出了相应条件下的最优算法．     

Q2,rj|sum|Cmin问题的半在线排序

本文研究两台平行同类机的一个半在线排序问题。当机器是有准备时间的同类机时,总加工时间已知,文章给出了一个竞争比至少为的半在线算法,同时给出了证明。     

工件有优先约束和尺寸的单机分批排序问题

研究了工件有优先约束和尺寸大小关系的分批排序问题,这里目标函数为工件的极大完工时间,这类问题是NP—完备的.对工件加工时间相同和有特殊到达时间的情况给出了它的近似算法,并证明其最差性能比不超过2.     

供应链管理中多制造商多客户的分批排序问题

研究每个制造商具有单台批处理机的多制造商、多客户的生产和运输集成问题,以生产和运输的总费用达到最小作为目标,建立问题的集成排序模型.在工件分别带有权重和交货期的情况下,在分析解的最优性条件的基础上,分别用工件的加权总完工时间和最大延主罡作为生产费用,给出相应的动态规划算法,并分析算法的复杂性.并且给出批容量有限加工时间都相同这一特殊情形的最优算法.     

带有一般性位置依赖影响的分组调度研究(英文)

为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的.     

无盘胜有盘 华硕服务器主析无盘系统应用方案

在一个网络中的所有客户端都不安装硬盘,而全部通过网络服务器来启动,这样的网络就是无盘网络.没接触过无盘网络的人可能会很快对这样的网络产生兴趣,每台服务省掉一个硬盘,一套六七十台机器的网络省掉的钱就相当可观,这可能是每个刚接触网络的人的第一印象.     

实际问题中的函数图象

《函数及其图象》一章中有一类联系实际的函数问题,画出这类问题的函数图象,是本章中的一个难点.许多同学在这里注意不够,作业中错误较多.下面我们用实例来研究这个问题. 一、实际问题中的一次函数图象例1 A市和B市分别有库存某种机器12台和6台,现决定支援给C市10台,D市8台.已知A市调运一台机器到C市、D市的运费为400元、800元,从B市调运一台机器到     

工件排序问题的最优解及其有效性

工件排序问题还没有已知的有效方法,希望有一个方法来得到一个相当好的解。由于工件排序问题可转化为双竞赛图与偶图,通过对匈牙利方法及Kuhn-Munkres方法的改进,分别可以得到二个有效的求工件排序问题最优解的方法。     

一类带批安装时间的平行机在线分批排序问题

研究一类带批安装时间的平行机排序问题。工件按时间到达,在任何时刻,只知道当前已经就绪工件的信息。工件成批加工,同一批中工件的完工时间为批中最后一个工件的完工时间,每批开工前有一个固定的批安装时间。目标函数为极小化所有工件的总完工时间。主要考虑两个到达时间且工件加工时间都相等的特殊情形,给出竞争比为3/2的在线算法,并且有实例说明此界为紧致的。