加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

工件加工时间为非线性分段函数的单机排序问题

讨论工件加工时间是开工时间非线性分段函数的单机排序问题，目标函数为极小化最大完工时间，总完工时间和加权总完工时间．对于目标函数为极小化最大完工时间和总完工时间的问题，给出了求解最优排序的多项式算法，对于目标函数为加权总完工时间的问题，给出了工件间的一致关系。     

加工时间离散可控的分批排序问题

分批排序和可控排序是两类重要的现代排序模型,该文中把这两类排序模型相结合,讨论加工时间离散可控的单机分批排序问题:对于所有工件具有相同的可控加工时间和控制费用这一情形,分别考虑机器容量有限及无限两种情况下,分别使最大完工时间和总完工时间加上加工时间可控所需费用的总和为最小作为优化的目标,讨论了这四个问题的最优解的性质,并在此基础上提出了相应的多项式时间最优算法.     

具有简单线性恶化加工时间的Flowshop调度问题

讨论工件具有简单线性恶化加工时间的FlowShop调度问题·对于两台机器目标函数为极小化最大完工时间的FlowShop调度问题,证明了利用Johnson规则可以求得最优调度·对于多台机器的一般FlowShop调度问题,如果工件在各机器上的加工时间均相等,目标函数为极小化最大完工时间或最大延误的问题可以转化为单机调度问题·如果目标函数为极小化完工时间和,则利用SPT规则可以求得最优调度·     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。     

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

讨论了工件加工时间依赖工件位置的链约束单机排序问题．对于链可中断和不可中断两种情形．证明了目标函数为最大完工时间和总完工时间时该问题仍然多项式时间可解．     

一类两机器 no-wait 流水作业总完工时间问题

在两机器 no-wait 流水作业问题中,每个工件在加工前有一调整时间,加工完之后有一移走时间,同一工件的调整和移走是可以重叠的,但加工时间不能重叠,同时任一工件在第二台机器上的加工必须紧接在它在第一台机器上的加工之后进行,本文以总完工时间为目标函数,讨论问题最优解中工件排列应满足的条件;其次讨论当工件的三种时间满足一定条件时最优时间表的求法;最后为问题设计了一个近似算法.     

加工时间线性恶化的成组加工流水作业问题

文章讨论了m台机器的Flow Shop成组加工问题.工件在不同机器上的加工时间以相同的系数(斜率)线性恶化.目标函数分别为极小化时间表长和总完工时间.对于目标函数为极小化时间表长的Flow Shop成组加工问题.再进一步细分为组间无调整时间和组间有相同调整时间的两种情形来讨论,都得到了最优调度(排序).对于目标函数为总完工时间的Flow Shop成组加工问题,只要组内按qij单调递增(SPT)序加工,组间按S.单调递增序加工可得最优调度.     

并行加工的完工时间

 p台机器完成加工n项任务所需要的时间称为这n项任务的完工时间.首先引入一种参数,即膨胀系数,并设计出一种加工n项任务的算法,然后分别讨论n项任务全都平均分成p份或者全都不分时被p台机器按所设计算法加工的完工时间.     

带到达时间的加工时间离散可控的单机排序问题1|rj , dm|Cmax +TPC的FPTAS算法

考虑工件加工时间离散可控的单机分批排序问题,目标函数是极小化最大完工时间与加工费用之和.对于工件不同时到达的情况,本文给出了FPTAS算法.     

同时具有学习和恶化效应的单机成组排序问题

讨论了一类工件的加工时间具有学习效应且安装时间带有恶化的成组排序问题,目标函数分别为极小化最大完工时间和极小化总完工时间,1｜pij=aij-bijt,S=δit,GT｜Cmax,1｜pij=aij-bijt,S=δit,GT｜∑Cij,并分别给出了求最优解的多项式时间算法,其中极小化总完工时间问题是在bij=b,δi=δ的特殊情况下给出的。     

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

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

具有学习效应的两台机器流水作业排序问题

讨论了具有学习效应的2台机器流水作业排序问题,目标函数为极小化总完工时间.首先证明了2个相关引理,基于2个引理和对问题的分析,证明了用SPT算法解决问题的界为一个与工件的最小加工时间和最大加工时间相关的且小于2的一个值.     

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

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

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

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

重新排序中目标函数与错位量的Pareto最优解

基于ε-约束的方法,研究了重新排序中目标函数与错位量的Pareto最优解问题,对于总完工时间或最大完工时间与时间错位量或序列错位量的Pareto最优解问题,本文给出了这些问题的多项式或拟多项式时间的算法.     

加工时间为线性增函数有上界的排序问题

本文讨论工件的加工时间是其开工时间的一类线性增加函数有上界的单机排序问题1|pj(t)(t0,T1,T2)|Cmax:设工件集J=J1,J2,…,Jn中的每个工件需要在一台机器上得到加工;工件集J被划分成两组J=Ω1+Ω2;机器上第一个被加工的工件在时刻t00开始加工;Ω1中工件的加工时间为pj(t)=ajt(当tT1)或pj(t)=ajT1(当t≥T1),Ω2中工件的加工时间为pj(t)=ajt(当tT2)或pj(t)=ajT2(当t≥T2),其中T2T1t0均是给定的常数,t表示对应工件的开工时刻;排序的目的是极小化时间表长(最大完工时间)Cm ax。在所得的引理2和引理3的基础上,本文给出一个复杂度为nlogn的多项式时间算法,从而也证明了所讨论的问题是多项式时间可解得的。     

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

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

订单带多类工件时的极小完工时间之和问题

该文考虑下述订单问题：m份订单中共有n个工件需要在同一台机器上加工，这n个工件分属五种不同的类，当机器从加工某一类中的工件转向加工不同于它的第j类工件时，需要一个安装时间Sj，机器加工第一个工件前也有相应于该工件所属类的安装时间，目标是寻找一个使得m份订单的完工时间之和最小的加工顺序，文中根据安装时间、订单完工的定义的不同，分了三种情形，并分别给出了多项式时间算法、分枝定界算法和启发式算法。     

具有可变时间的并行排序问题

设有p台处理机要加工n项任务，当每项任务t在时刻i和处理机j上被开始执行时，都有一个不可间断的加工时间l(t，i，j)∈{k1，k2}，我们的目标是要找一个可行方案σ，使得总的完工时间最短．该问题是NP-完备的，本文给出该问题的一个近似算法。