带准备时间的同类机半在线问题的近似算法

研究了带机器准备时间的两台同类机已知工件最大加工时间的半在线排序问题,讨论了极小化最大工件完工时间这个目标函数,并给出了一个竞争比为分段函数的近似算法.     

具有维修时间的两台平行机在线排序

在排序问题中,机器可能出现故障或其他原因而需要维修,因此,在加工工件时把维修时间考虑进去是很必要的.对机器维修时间完全重合、可中断的两台平行机排序问题,本文考虑它的在线情形.通过分析不同情形,给出其任意在线算法竞争比的下界为2,并给出一个最好可能的在线算法.     

单台机器有使用限制的排序问题

研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.     

带准备时间的两台同类机半在线排序

针对机器速度和准备时间不同,探讨了带机器准备时间的两台同类机半在线排序问题,以达到优化工作效率的目的.目标为极小化最大机器完工时间,对于所有工件中最大工件的加工时间已知的这种半在线情形,给出了一个竞争比不少于(s+1)/(2s+1)的MIN半在线算法.     

带有不可用区间的批运输排序问题

在实际生产中,因机器在加工过程中发生故障或维修等原因而使机器在某一区间不可用。在同一批的工件一起运输给客户,且批的完工时间依赖于这批中最后一个工件的完工时间,即批的完工时间等于这批中最后一个工件的完工时间。文章中批交货期等于批的完工时间,因此工件的流水时间等于该工件所在批的批交货期。考虑的是n个独立的工件在单台及2台平行机的问题,并且机器带有不可用区间且是不可恢复的排序问题。运输费用依赖于批数。目标函数是极小化总流水时间及运输费用之和。对于机器在任意时间段维修的情况,分别给出了单台及2台平行机的排序问题的拟多项式的动态规划算法及相对应的时间复杂性。     

两阶段供应链下极小化最大完工时间的单机系列批排序

【目的】考虑单机情况下的加工和运输两阶段的供应链排序问题。【方法】在生产阶段,将所有工件在加工之前划分成批,在一台有限批容量的机器上加工,工件的实际加工时间是关于该工件退化率和加工位置的函数;在运输阶段,有一辆运输车,且每次只能运输一批工件,即车的容量等于批的容量。通过分析用运输车的车容量限制与工件个数的关系。【结果】由最优算法得到了一个最优排序和最小化最大完工时间。【结论】首先给出最大完工时间问题的一个下界,然后指出在当工件个数小于等于运输车的容量限制时,提供出来一个最优算法。对于当工件个数大于运输车的容量限制时,证明了当工件满足一定条件时,该问题也存在最优算法。     

同类机随机在线排序模型及算法分析

考虑同类机随机在线排序问题.假设有m台同类机,工件在线到达,问题的目标是使总加权完工时间的期望值最小.考察该随机在线问题,首先利用线性规划松弛的方法,得到问题最优解的一个下界;然后给出解决该问题的一个在线算法,并分析了该算法的竞争比.     

流水作业排序问题的启发式算法

研究了n个工件在2台机器下的流水作业排序问题,目标是使加权完工时间最小.同一工件在一台机器上完工后与在另一台机器上开工前存在一定的时间间隔,将其定义为运输时间,所有运输过程均由单自动机完成.讨论了该排序问题的复杂性,并引入了一种启发式算法,证明了该问题是强NP困难的,该算法的紧界为3/2.     

具有预约到达时间的平行机在线排序问题研究

以现代服务业预定系统中的实际问题为背景,研究了一类具有预约到达时间和最迟完工时间的在线排序问题;论证了两台机器时该问题的在线算法竞争比下界为2;在传统在线排序算法的基础上提出了针对该问题的在线贪婪算法,并分析了该算法的竞争比.     

两台带准备时间的同类机的半在线排序

研究了带机器准备时间的两台同类机的半在线排序问题,这里目标函数为极小化最大机器完工时间.对于所有工件总的加工时间已知的半在线情形,我们给出了一个竞争比为max{52 1,1 bb}的半在线算法,其中b为机器速度.并且算法对于对于机器加工速度b<2时的同型机情形是最好的.     

工件可拒绝的分批配送问题研究

考虑工件可拒绝的分批配送问题:一个制造商为一个客户加工n个工件,每个工件既可以被接受加工,也可以被拒绝加工(但要支付拒绝费用),工件加工完之后要安排车辆运送给客户,完工时间为工件送达客户的时间.目标函数为被接受工件的总完工时间、总配送费用和被拒绝工件的总拒绝费用三者之和,文中对处理机为单机的情形给出了多项式时间算法,且证明了两台平行机的情形下该问题是NP-完备的,并给出了伪多项式时间算法.     

具有交货时间的单机作业调度问题的最优解

基于回溯思想的算法通过系统地搜索解空间可以得到具有交货时间的n个作业的单机作业调度问题的最优解.给出一种改进算法,使得算法的时间复杂度由O(n!)降低到O(nlgn).     

有界平行批处理机的在线排序问题

主要研究的是在线运输排序问题,即研究m台有界平行批处理机上考虑工件运输的在线排序问题.工件按时间在线到达,即一个工件只有在被释放之后才能知道它的一切信息.这些工件首先要在平行批处理机上分批加工,然后加工完成的工件再被一个运输车辆运送给某个顾客.当车辆的容量是充分大的时候,给出一个最好可能的在线算法,其竞争比为(5(1/2)+1)/2;当车辆的容量有限时,给出一个竞争比为(5(1/2)+3)/2的在线算法.     

锁定初始调度的紧急工作单机重调度问题

对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(reschedulingrushjobswithloadslockedonsinglemachine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.     

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

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

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

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

同时具有学习效应和恶化效应的机器可用限制性排序问题

针对单机和两台机器的平行机排序问题,建立了工件同时具有学习效应和恶化效应,机器有可用性限制的排序模型.考虑了目标函数为极小化总完工时间的单机、两台机器的同型机问题和两台机器的同类机问题.对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法.     

Minimizing Maximum Lateness on Unbounded Single Batching Machine with Family Jobs

The scheduling problem on a single hatching machine with family jobs was proposed.The single hatching machine can process a group of jobs simultaneously as a batch.Jobs in the same batch complete at the same time.The batch size is assumed to be unbounded.Jobs that belong to different families can not be processed in the same batch.The objective function is minimizing maximum lateness.For the problem with fixed number of m families and n jobs,a polynomial time algorithm based on dynamic programming with time complexity of O(n(n/m + 1)m) was presented.     

带有维修活动和工件可拒绝的单机排序问题

讨论了带有交货期、维修活动和工件可拒绝的单机排序问题,这一问题是将所有的工件分成2个集合,分别是被接受的工件集和被拒绝的工件集。规定每个被接受的工件都有一个待定的交货期,且所有工件的交货期的大小相同。如果工件在交货期内完工,则不产生任何费用,否则工件提前或延误,会产生相应的提前或延误的费用。而对于拒绝工件而言,它的费用只与工件有关。维修活动需要在一个固定的时间长度内完成,排在维修活动之后的工件的加工时间将会减少。这类问题的总费用是2个工件集的费用之和,目标函数是确定被接受工件的最优排序,极小化接受工件和拒绝工件的总费用,该问题在多项式时间可解,在今后的应用中能发挥作用。