单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

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

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

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

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

一类三机器流水作业极小化加工全长问题

一般的三台机器流水作业的加工全长问题为强NP困难的．本讨论它的特殊情形，即第二台机器上工件的加工时间均相等．我们证明了该问题仍为强NP困难的，并构作了一动态规划算法，最后讨论问题的可求解情形．     

FMS生产调度的参数优化

基于离散事件动态系统的线性系统理论，本文研究了ＦＭＳ的最大机床利用率问题。只靠作业排序和托盘优化不能有效地改善各机床的负荷平衡，选择适当的工件输入比例，可以使各机床都达到最佳利用率，这不仅是一个静态负荷平衡的问题，它还影响系统的动态运行过程和工作周期。本文分析了各种因素对机床利用率的影响，将工件输入比例优化归结为一个整数规划问题，并给出了算法和例题。     

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

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

工序问题的动态规划算法

提出了一个求解工序问题的动态规划算法，该算法排序含ｎ个工件集合的期望时间为Ｏ（ｎ）．     

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

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

线性加工时间单机成组排序问题

讨论一类线性加工时间成组排序问题．在这一模型中，工件的加工时间是其开工时间的线性函数，全部工件分成若干组．工件的加工必须满足成组技术限制，同组工件间没有安装时间，各组间有与顺序无关的安装时间．目标函数为极小化最大完工时间．基于对问题的分析，给出了多项式算法。     

随机加工时间的单机随机调度问题

讨论了加工时间服从均匀分布的单机随机调度问题，目标是使拖后工件数的数学期望最小．采用理论分析的方法，给出了期望加权误工任务数的表达式，研究了工件的最优加工顺序．结果表明：在工件的权重和工件的平均加工时间不成比例的最一般的情况下，最短加工时间和最长加工时间优先规则的联合使用给出了使拖后工件数最少的优先策略，并对算法的最优性进行了证明．该成果对于非正规目标函数的单机随机排序问题的解决具有一定的参考价值和指导意义．     

具有周期维护的最小化工件完成时刻之和的平行机调度问题

考虑具有周期维护的m台平行机调度问题,一组给定的工件在这些机器上加工,目标是给出工件完成时刻和最小的调度方案。基于经典的SPT(最短加工时间优先)算法,提出了名为MSPT的启发式算法,并证明了该算法优于SPT算法。     

平行机上有优先约束的工件的排序问题

考虑有优先约束的单位工件在m台同型机上的排序问题，目标函数是使工件的完工时间之和最少，当机器的台数不确定时这个问题已经得到了解决．该文中指出当机器的台数确定为m(m≥3)时该问题是NP-完备的。     

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

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

以总加权完工时间为目标的两台机越库排序的动态规划算法

提出并研究两台机器环境下的以带权总完工时间为目标函数的越库配送排序问题.越库作业的入库与出库车辆被看作是排序问题中的机器,入库货物与客户需求为具有前序集限制关系的被加工工件.研究了该问题的计算复杂性及其最优解的若干性质,提出求解该问题的逆向动态规划算法,并给出了动态规划算法的数值实验.结果表明,所提出算法至少可以求解25个工件规模的越库配送排序问题.     

平行批排序最小化最大完工时间在线算法的一个注记

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,NavalResearch Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algo-rithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为(5 1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1 α)r αp时刻以后加工,其中α=(5-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.     

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

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

自由作业稠密时间表的性能比上界

对于自由作业问题，如果从初始时刻开始，逐步在每个机器安排任一可以加工的工件，避免不必要的空闲，所得的安排称为稠密时间表。其加工总长与最优值之比具有上界２－１／ｍ（ｍ为机器数），是一个尚未证明的猜想。本文引入了最后工件组及相关机器集的概念，证明了ｍ＝５时该猜想是成立的。     

强制工期相等的双机流水车间排序问题

讨论了强制工期相等的n个工件在双机流水车间的加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会不可行排序.先讨论问题的可行性,如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后,给出一个多项式时间算法,在预排序列的基础上,通过调整最先加工的工件来获得最优排序.     

面向分段涂装作业的混合流水车间调度

基于船舶分段涂装作业,提炼出具有重入和等待时间约束的两阶段混合流水车间调度问题.其中第一阶段含多台批处理机,第二阶段含多台离散机且存在一次重入过程,两阶段间有等待时间约束.以最小化最大完工时间为优化目标建立数学模型,提出一种结合Metropolis抽样准则和变邻域搜索的混合量子粒子群优化算法,并利用多种启发式规则进行解码.实例验证和数值分析表明,所提算法是解决分段涂装调度问题的一种有效方法.