具有学习效应和非线性安装时间的单机排序问题

讨论了加工工件具有学习效应和安装时间的单机排序问题。文中工件的加工时间不是固定不变的,不仅与工件的加工位置有关,同时还与已加工完成工件的加工时间有关。安装时间分为线性安装时间和非线性安装时间,本文主要讨论的是具有非线性安装时间的情况。工件的安装时间是依赖于已加工完的工件的实际加工时间和工件所排列位置的函数形式。在文中主要证明了极小化最大完工时间,极小化完工时间总和问题是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误问题是多项式可解的。     

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

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

带有交货期窗口和加工时间可控的排序问题

讨论了带有交货期窗口和加工时间可控的单机排序问题。工件的加工时间是关于分配资源量的凸函数模型。工件若在交货期窗口前完工,则产生提前费用;若在交货期窗口后完工,则产生延误费用。分别研究了多窗口问题和单窗口问题。目标是在关于提前、延误、交货期窗口开始时间、交货期窗口大小和最大完工时间的函数约束条件下,确定工件的最优加工顺序、最优加工时间、极小化资源费用函数。通过将2个问题分别转化为指派问题,证明了2个问题是多项式时间可解的,问题的计算复杂性是O(n3)。     

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

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

带退化效应和不可用区间的并行批处理机问题

本文研究的是一类带有不可用区间和线性退化效应的单机无界并行批处理机排序问题。工件开始加工时间的线性递增函数看成其实际的加工时间。批工件中加工时间的最大者为这批的加工时间,同批工件同时开始加工,且批一旦开始加工就不可中断,同批中工件的完工时间都相同并为这批的完工时间。本文通过对最优解性质的分析,分别给出了求解极小化最大费用和极小化总费用的拟多项式时间算法。特别当k固定、目标函数为误工工件数时,该问题为多项式时间可解的,并用数值例子验证了算法的有效性。     

非对称模糊加工时间工期指派调度优化问题的一类多项式求解算法

针对工件加工时间为非对称模糊数,极小化提前完工惩罚和拖期完工惩罚之和的均值的单机工期指派调度优化问题展开研究.证明了当模糊加工时间具有相同宽度比时,该问题是多项式可解的,并 给出了多项式求解算法.同时根据历史数据,构造了工期指派问题的调度模型,并利用所给出的算法求得最优解,从而 表明所提出的模型和算法的有效性.      

带退化效应和不可用区间的并行批处理机问题

本文研究的是一类带有不可用区间和线性退化效应的单机无界并行批处理机排序问题。工件开始加工时间的线性递增函数看成其实际的加工时间。批工件中加工时间的最大者为这批的加工时间,同批工件同时开始加工,且批一旦开始加工就不可中断,同批中工件的完工时间都相同并为这批的完工时间。本文通过对最优解性质的分析,分别给出了求解极小化最大费用和极小化总费用的拟多项式时间算法。特别当k固定、目标函数为误工工件数时,该问题为多项式时间可解的,并用数值例子验证了算法的有效性。
     

具有加工顺序约束和非对称模糊加工时间的工期指派调度方法

研究了工件加工时间是非对称模糊数、工件间具有优先加工顺序约束、目标函数为极小化提前完工惩罚和拖期完工惩罚和的均值的单机工期指派调度优化问题.证明了当模糊加工时间具有相同宽度比、优先加工约束关系为树状约束时,该问题是多项式可解的.进一步,当优先加工顺序为一般约束时,基于线性规划松弛技术,设计了近似比为2的近似算法.      

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

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

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

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

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

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

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

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

有调整时间的两机器流水作业总流程问题

在两机器流水作业问题中 ,每个工件在加工前有一调整时间 ,同一工件的调整是可以重叠的 ,但加工时间不能重叠 .本文以总流程为最优准则研究调整时间独立于加工时间的两机器流水作业问题 ,给出了问题最优解中工件排序应满足的条件 ;其次讨论当工件的两种时间满足一定条件时最优时间表的求法 ;最后给出几个近似算法     

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

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

产品中各工件在单台机器上加工时的排序问题

本文考虑的是工件在单台机器上加工随后组装成产品的排序问题．每个产品由一个特殊工件和一个共同工件组成,机器从加工特殊工件转到加工共同工件有一个调整时间,目标是使所有产品完工时间在批可达或工件可达情况下的加权和最小．对两种情况我们都给出了多项式时间算法．     

具有学习效应和遗忘效应的间歇批生产的单机排序问题

本文研究具有Dejong学习效应和遗忘效应的间歇批生产的单机排序问题,考虑了批与批之间没有学习效应的传递、有部分学习效应的传递和有总的学习效应传递的三种模型.对目标函数为最大完工时间的情形,指出机器在批与批之间没有学习效应的传递和有部分学习效应传递的情形下是多项式可解的,并进一步对机器在批与批之间有总的学习效应传递的两种特殊情形给出了多项式时间算法.     

带有交货期窗口和工件可拒绝的单机排序问题

讨论了带有交货期窗口和工件可拒绝的单机排序问题﹐这一问题是将所有的工件分成两个集合﹐一个是被接受的工件集﹐一个是被拒绝的工件集。假设被接受的每个工件都有一个待定的交货期窗口﹐且所有工件的交货期窗口的大小是相同的﹐如果工件在窗口中完工﹐则不产生任何费用;否则工件提前或延误﹐会产生相应的提前或延误的费用。而对于拒绝工件而言﹐它的费用只与工件有关。这类问题的总费用是2个工件集的费用之和。目标函数是确定被接受工件的最优排序﹐极小化总费用﹐给出了一个动态规划算法﹐并证明了这个问题是多项式时间可解的。