一类具有学习效果的单机排序问题

讨论一类具有学习效果的单机排序问题.在这类问题中,由于学习效果的作用,工件加工时间将逐渐减少.学习效果通过工件正常加工时间的分段线性函数来描述.基于对问题的分析,把目标函数为极小化总惩罚的工期确定问题转化成指派问题,从而得到问题的多项式算法.对于极小化完工时间和与完工时间偏差的双目标问题,其一般情况同样可以转化成指派问题.此外,对于某些特殊情况,给出了极小化最大完工时间问题与完工时间和问题的简便算法.     

离散加工时间单机多准则下可控排序问题

讨论了工件具有离散可控加工时间的单机多准则下的排序问题. 目标函数分别为极小化完工时间和与完工时间偏差和的线性组合, 极小化等待时间和与等待时间偏差和的线性组合, 极小化提前时间、延误时间、最早交货期及窗口长度的加权和, 极小化提前时间、延误时间及公共工期的加权和. 用数学规划的方法证明了四类多准则下的单机排序问题可以转化为指派问题,从而这四类问题都多项式时间可解.     

具有学习与退化效应的单机排序问题

研究了具有学习效应与退化现象的单机排序问题,给出了目标函数为最大完工时间、总完工时间的多项式时间算法;并证明工件的权重与加工时间一致时加权总完工时间问题、工期与加工时间一致时最大延迟问题均有多项式时间算法.     

一类具有维护和共同工期的单机排序问题

主要讨论了带有维护和共同工期的单机排序问题.工件的实际加工时间是与该工件在排序中的加工位置相关的.目标函数是共同工期相关的费用、提前完工的工件存储费用和不能在工期内完成的工件的惩罚费用之和.最后给出了多项式动态规划算法.     

一类最优排序具有∨或∧型特征的随机单机调度问题

本文讨论了一类加工时间随机，机器随机故障的单机调度问题，其目标函数为：（ｉ）完成时间的平方和；（ｉｉ）平均完成时间的平方；（ｉｉｉ）平均完成时间的线性组合的期望，文中首先给出了当与机器随机故障相关的点过程为广义泊松过程时，目标函数的确定形式，然后给出了使目标函数最小的最优排序依加工时间的期望具有∨型或∧型特征的条件。     

序列错位下完工时间和的随机重新排序问题

讨论了工件加工时间服从任意分布的随机重新排序问题,目标是使期望总完工时间最小.根据理论分析的方法,研究了工件的最优加工顺序.结果表明最短期望加工时间优先规则是使目标达到最小的策略,并由该策略得出多项式时间算法.     

具有工期限制的退化工件单机排序问题

工件具有退化效应的排序问题最近几年受到人们越来越多的关注。所谓具有退化效应的工件是指在排序中,工件的开工时间越晚其实际的加工时间就越长。讨论了一类具有工期限制的线性退化工件单机排序问题。其中线性退化工件指的是工件的实际加工时间是线性增长的函数。文中工件的实际加工时间不是固定不变的,是该工件的开始加工时间的单增函数。目标函数是使完工时间,提前完工时间和误工时间的加权和最小。给出了多项式时间的最优算法。     

一类最优排序具有∧型或∨型特征的随机单机调度问题

本文讨论了一类加工时间随机、机器随机故障的单机调度问题．其目标函数为：（ｉ）完成时间的平方和，（ｉｉ）平均完成时间的平方，（ｉｉｉ）平均完成时间的线性组合的期望．文中首先给出了当与机器随机故障相关的点过程为广义泊松过程时，目标函数的确定形式，然后给出了使目标函数最小的最优排序依加工时间的期望具有∨型或∧型特征的条件．     

时间期望错位限制下完工时间和的随机重新排序

讨论了工件加工时间服从任意分布,在时间期望错位下的随机重新排序问题,目标是使期望总完工时间最小.根据理论分析的方法,研究了工件的最优加工顺序.结果表明最短期望加工时间优先规则是使目标达到最小的策略,并由该策略得出多项式时间算法或拟多项式时间算法.     

批数确定的分批排序问题最优解的结构性质

研究了目标函数为总完工时间、工件恰分N批的单机分批排序问题最优解的结构性质,其中N为1与工件数之间的任意整数.分批方式为继列分批和平行分批.     

多项式可解的单机加权E/T调度问题

研究了目标函数为完成时间与交货期差平方的加权和的单机调度问题，在工件的权值与加工时间成比例时，给出了问题的最优解．然后，在假设描述机器随机故障次数的计数过程为广义泊松过程时，将上述结果推广到机器有随机故障的情形．     

具有窗口交货期的单机E/T调度问题

工件完成时间与交货期差的绝对值加权和最小化单机调度是典型的E／T(Earliness／Tardiness)的调度模型，是NP-hard问题．然而，当工件权值与加工时间成正比时，LPT(Largest Processing Time)工件调度最优．本讨论了上述问题具有窗口交货期且工件权值与加工时间成正比的情形，结果表明LPT工件调度仍然最优．     

一致性条件下带磨损因子的排序问题

考虑下述带磨损因子的排序问题：n个工件需在同台机器上依次加工，工件j,j=1，2，…，n,所需的加工时间同它被开始加工的时间有关，当工件j开始被加工的时间为t时其所需的加工时间为Pj=bjt，其中bj可视作与工件j有关的一个磨损因子．要求适当排列这n个工件的加工顺序，使某目标函数值达最小．对最大迟后、最大延误、加权完工时间之和这三个目标函数，文中给出了相应条件下的最优算法．     

Two single machine scheduling problems with a learning effect

研究工件具有学习效应的两个单机排序问题.工件的学习效应指的是工件的加工时间为所排位置的函数. 对以下两个目标函数:加权总完工时间与最大延误, 证明在某些特殊情况下加权最小加工时间优先(WSPT)规则和最早工期优先(EDD)规则可以分别给出最优算法. 也给出了这两个规则在一般条件下的最坏情况界.     

具有正比权值完工时间与交货期偏差加权和最小化单机随机调度

完工时间与交货期偏差加权和最小化单机调度(简记TWD)问题是Just—In—Time生产环境下典型的调度模型，是NP—hard问题．然而工件权值与加工时间成正比时，LPT(Largest Processing Time)调度最优．本考虑了随机TWD问题，其中工件的加工时间和交货期都服从指数分布，证明了LEPT(Largest Expected Processing Time)调度的最优性，并进一步将结论推广到机器随机故障的情形．     

机器具有可用性限制的加权总完工时间问题

研究一种带有学习和恶化效应,并且机器具有可用性限制的排序问题。讨论的目标函数为加权总完工时间的单机和两台机器的平行机问题。在某些实际生产过程中,工件加工时间的变化既受生产设备长时间使用,导致恶化现象的影响,也受生产设备或工人加工效率提高的影响。因此,在这种模型中,工件的实际加工时间不仅与它的所排位置有关,而且还与工件的开始加工时间有关。此外,由于机器发生故障或进行维护与保养等原因,导致其在某一区间内无法加工工件。针对某种学习和恶化效应模型下机器在任意时间段维修的单机和2台机器的平行机的某些情况,分别给出了拟多项式时间动态规划算法,分析了算法复杂性,并给出相应数值例子表明算法的有效性。     

一类带折扣加权总完工时间单机排序问题

讨论了工件加工时间和排列中位置相关的单机排序问题．对工件加工时间和位置相关的两个线性模型Pi(v)=ai-biv和pi(v)=aiv^-b进行了讨论，目标函数是带折扣的加权总完工时间,并且对工件加工时间与给定权值之间具有一致关系的某些情况给出了最优算法。     

极小化加权总完工时间的工件可拒绝排序 (运筹学与控制论)

经典的排序问题要求工件都必须进行加工,然而在实际中有时候由于一些特殊的原因可以考虑工件不加工。例如,加工时间非常大,或加工所需费用非常高,于是就不加工这一工件,而是通过支付一定的费用后送到外边"外加工"或购买更合算,这类问题称为工件可拒绝排序问题。需要研究的任务是怎样选择工件在机器上进行加工或拒绝,并且如何安排被接受加工工件的加工次序使给定的目标函数值最优。本文研究了工件可拒绝排序中,目标函数是有限的总惩罚费用(总惩罚费用约束下)极小化加权总完工时间,工件到达时间都相同的同型机问题,设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法。     

退化条件下的工期指派的单机排序问题

研究退化条件下的工期指派的单机排序问题。每个工件均有一个关于工期的连续非减的惩罚函数。工件的加工时间是退化的,即工件的加工时间是其开始加工时间的一个线性增函数,所有工件都有一个相同的退化率。目标是确定工件的最优加工顺序、最优工期和最优开始加工时间,使总工期、误工工件数及总完工时间之和最小。工件在工期之后完成则称为误工工件,工件在工期之前完成则是提前工件。工期指派分两种情况,一种是所有的工件工期都相等,另一种是不同的工件有不同的工期。对于上述两种情况分别给出了最优解的3个性质,并且证明了这个问题是多项式时间可解的。