一种极小化∑wjCj的分批排序问题的算法

讨论了单机分批排序问题中目标是极小化加权总完工时间的问题．对于所有工件的加工时间都相等的情况，分别对常数个到达时间和任意个到达时间的情况给出了两个最优算法，并给出了其算法复杂性．     

集成多种工件生产与配送的排序问题

考虑了多个客户订购不同种类的工件,工件生产完后需要运输到客户的单机供应链排序问题.由于工件属于不同的种类, 在加工不同种类工件前要有一个准备时间.加工完成的工件分批配送到相应的客户处,每一批配送需要花费一定的时间及费用.考虑了两个目标函数,并分别给出了它们的最优算法.     

1|B,rj∈{0,r}|∑Cj问题的复杂性及近似算法

讨论了分批排序中工件有两个到达时间、以工件完工时间总和目标函数的批处理问题，证明了其ＮＰ－完备性，并以Ｂｒｕｃｋｅｒ等给出的动态规划算法为基础，给出了一性能指标为２的多项式时间近似算法。     

两个带有分批费用的单机平行分批排序问题

假定工件和批处理机都在零时刻到达,工件被成批进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用。第1个问题对目标函数为任意的正则函数与分批费用之和的情形,利用动态规划方法给出了拟多项式时间算法;第2个问题对目标函数为误工工件数与分批费用之和的极小化问题,同样利...     

工件尺寸不同的平行机分批排序

研究了工件有尺寸大小在平行机上的分批排序问题，这里目标函数为工件的极大完工时间，这类问题是m完备的，对同型机情况，给出了它的近似算法PM，并运用了拆分的技巧，证明它的最差性能比不超过11/4-1/m。     

最小化时间表长的带有多个工件组单机无界继列批在线排序

考虑了批容量无界情形下带有多个工件组的单机继列分批的在线排序间题.每个工件具有各自的安装时间和加工时间(s,p),属于不同组的工件不能在同一批中加工,目标函数是最小化最大完工时间,给出了此问题的一个竞争比为2的最好可能的在线算法.     

1|B,r_j∈{0,r}|ΣC_j问题的复杂性及近似算法

讨论了分批排序中工件有两个到达时间 ,以工件完工时间总和为目标函数的批处理问题 ,证明了其NP_完备性 ,并以Brucker等[1] 给出的动态规划算法为基础 ,给出了一性能指标为 2的多项式时间近似算法     

一种极小化ΣwjCj的分批排序问题的算法

讨论了单机分批排序问题中目标是极小化加权总完工时间的问题.对于所有工件的加工时间都相等的情况,分别对常数个到达时间和任意个到达时间的情况给出了两个最优算法,并给出了其算法复杂性.     

带学习效应的极小化全总完工时间的分批排序问题

讨论了分批排序中工件具有带学习效应、目标函数为极小化加权总完工时间两个问题,分别就所有工件的加工时间都相等的情况给出了两个算法,并证明了这两个算法的最优性.     

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

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

批处理机上有就绪和截止时间的等长度工件排序

一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题,目标是求一个可行时间表.就该问题,Baptiste已经提出了一个复杂性为O(n8)的算法,在此基础上,本文推广Garey等人关于对应的经典排序问题的算法,得到了一个复杂性为O(n2)的算法.算法分两个阶段执行:在阶级I,算法找出所谓的禁止开工区间,在这些区间中将不允许有工件开工;在阶段II,算法从时刻零开始,每当机器有空闲且不属于禁止开工区间的时候,就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工,若当前的机器空闲时刻属于某个禁止开工区间,则首先更新其到该禁止开工区间的右端点再进行决策.     

工件分簇的半连续型批处理机调度问题

半连续型批处理机调度问题是从钢铁工业加热炉对管坯的加热过程中提炼出来的,其中把加热炉看作批处理机,同一时刻可以有C个工件被加工。工件以批方式进行加工,批中工件的进入、加工和离开都是按周期进行,同一批中的工件都有自己的开始加工时间和完工时间,且加工时间均等于这批工件中加工时间的最大者,批的大小为这批工件的个数。半连续型批处理机调度问题包含如何分批及安排各批间的加工顺序。考虑了单机且工件分簇的情况,其中在同一簇中工件的加工时间相同。目标函数为极小化总完工时间。对于工件的簇数是F的情况,通过最优解的性质给出了一个复杂性为O（F^2）的动态规划算法,能够获得对应问题的最优解。     

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

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

重加工具有退化与学习现象的单机批排序问题

本文对同一台机器下次品工件可重加工生产的问题进行研究。工件要求成批加工,每批包括连续加工的两个子批。第一子批的工件加工后,一部分工件是按照要求得到的优良品,另一部分工件是次品。次品的工件接着在第二子批重加工,而次品工件在等待重加工时会产生退化与学习现象,加工完成后得到的工件是优良品。同一子批的工件同时完工,工件的完工时间是该子批中最后一个工件的完工时间。假设每批生产的工件次品率是相同的。每一批工件开始加工和重加工时都有安装时间。目标函数是使总安装时间,重加工和库存持续费用最小,并且优良品工件的需求得到满足。对于该问题的一般情形给出了动态规划算法。接着当批工件的完工时间和批的规模满足一致关系,给出多项时间算法。     

最优公共交货期单机提前/拖后调度和对应的批次送货

本文考虑了一个包含工件生产和工件送货的单机调度问题。目标是寻找所有工件的公共交货期和每个工件的送货时间使得工件所受到惩罚(提前／拖后惩罚,送货费用等)的值最小。完成的工件按照批次进行送货,所有在公共交货期前完工的工件在最优交货期时间一起交付,对批次送货没有量的约束。本文确定了最优公共交货期,并给出了相应的排序。     

无容量限制的批处理机时间表问题

研究无容量限制的批处理机时间表问题，在工件有到达时间和工期约束下，证明了当工件的到达时间和工期，或到达时间和加工时间一致单调时，该问题是多项式时间可解的；当加工时间和工期一致单调时，该问题是NP困难的。     

P与d一致时的分族分批排序误工个数问题

研究了一类分族分批排序最小误工个数问题,给出并证明了最优排序的性质,证明了此问题是NP-困难的．对工件的到达时间和工期一致时的情形,给出了一个时间复杂性为O（mb（n/m）^2m）的动态规划算法．     

具有到达时间和禁用区间的单机平行批排序

研究工件带有到达时间且机器带有可用性限制(禁用区间)的单机平行批排序问题.假设机器在一些不交的时间区间上不可用.工件以平行批的形式在机器可用的时间区间上加工,并且不可中断.一个批的加工时间是这一批中加工时间最长的工件的加工时间.对任意的正则目标函数,当工件带有到达时间且机器带有可用性限制时,给出了单机平行批排序问题的一个拟多项式时间算法.     

工件有到达时间的平行机分批排序问题的一个PTAS算法(英文)

研究工件有到达时间的最小化加权完工时间和的平行机分批排序问题,通过综合运用实例转换,工件分类和动态规划等方法提出了一个多项式时间近似框架.     

应用混合蚁群算法求解并行批处理机组批与调度问题

晶圆制造系统的批处理机具有长加工时间的特征,其调度性能指标对车间总体绩效有重要影响.批处理机调度分为组批与批次调度.针对工件的动态到达特性导致组批困难,提出了一种混合型蚁群算法.利用该算法的全局并行搜索能力对工件进行组批,并使用BATC算法对批次进行调度,可以解决多产品并行批处理机调度问题.以工件总拖期最小为性能指标,通过实例仿真,对蚁群算法性能进行分析评价和比较.结果表明,所提出的算法具有有效性和实用性.