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

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

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

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

一类带有可控加工时间的单机排序问题 (运筹学与控制论)

讨论了具有学习效应的工期指派和可控加工时间的单机排序问题。工件的实际加工时间同时依赖于所排位置和所分配的资源消耗相关的函数,资源消耗分为线性和凸资源消耗2种。考虑共同工期、松弛工期和没有限制的工期3种工期分派方法。目标是确定工件最优的加工顺序、工期和资源分配量,极小化一个包含提前、延误、工期分派、总完工时间和总资源消耗的总费用函数。对于上述2种不同资源消耗函数与3种不同的工期分派方法的每一种组合,均给出了多项式时间算法。     

带有学习及退化效应和资源分配的交货期指派的单机排序问题

本文讨论带有学习及退化效应和资源分配的交货期指派的单机排序问题。所有工件有一个公共的交货期,如果工件在交货期内完工将不产生任何费用,但是在交货期之前或之后完工将产生相应的提前或延误费用。工件的实际加工时间是与开工时间、在排序中位置和资源分配有关的函数。目标是确定最优交货期的位置、交货期的大小、工件的最优排序和最优资源分配,最小化包括提前、延误、交货期大小、交货期位置和资源消耗的总费用。证明了带有学习及退化效应和资源分配的交货期指派问题仍然是多项式可解的,并且最优算法是可以在O n()3时间内求出最优解。     

带有多个工期窗口及退化维护的单机排序问题

【目的】讨论带有多个工期窗口及退化维护的单机排序问题。【方法】工件的加工时间是一个和资源分配、工件在排序中的位置以及退化效应有关的凸函数。目标是确定多个最优工期窗口的位置和大小、指派给每个工期窗口的工件集合、分配给每个工件的资源、最优的维修位置和最优的工件排序,最小化提前、误工、工期窗口的开始时间、工期窗口的大小、资源分配、时间表长的总费用。【结果】证明了带有多个工期窗口及退化维护的单机排序问题仍然是多项式可解的。【结论】最优算法是可以在 O ( n4 )时间内求出最优解。
     

带有机器维修和多个工期的单机排序问题

针对具有恶化工件和机器维修的单机排序模型,讨论了多个工期的指派问题。在这一模型中,机器在加工过程中产生恶化使效率降低,工件的实际加工时间是关于开始加工时间的线性递增函数;机器的维修区间是关于开始维修时间的线性递增函数,维修工作完成后,机器将恢复到初始状态,工件的恶化也重新开始。目标是确定最优排序、最优工期和最优维修位置以便极小化工件的提前、延误和工期的总费用。对于这一问题,给出了最优解的一些相关性质,证明了这个问题是多项式时间可解的。     

带有恶化效应和维修恶化的单机工期指派问题

本文研究了同时带有恶化工件和机器恶化维修的单机工期指派问题。工件的实际加工时间是与工件基本加工时间和工件在排序中的实际加工位置相关的一般函数。机器维修时间与其开始维修时间有关,是其线性恶化函数。研究的目标函数是加权提前、延误和工期之和,目的是确定工件的最优加工顺序、公共工期及维修位置,使目标函数最小。将此问题转化为指派问题,从而证明了该问题在多项式时间内是可解的。对于问题的一种特殊情况进一步给出了一个复杂性为O(n2logn)的最优算法。
     

具有学习效应且加工时间可控的单机排序问题

讨论一类加工时间可控的单机排序问题.在这一问题的模型中,机器具有学习效应,工件的实际加工时间为同时依赖于所排位置和所分配的资源量的资源消耗函数,其中资源消耗函数又分为线性资源消耗函数和凸资源消耗函数这两种函数.考虑共同工期分派方法和松弛工期分派方法这两种工期分派方法.极小化一个包含加权总误工数的费用、工期分派的费用、最大完工时间的费用和总资源消耗的费用的目标函数.对于工件加工时间的两种资源消耗函数与工期分派方法的不同组合,算法复杂性为O（n4）的多项式时间算法相应地被给出.创新之处是：在Shabtay研究的基础上增加考虑了学习效应后,计算相关问题的算法复杂性仍保持不变.     

加工时间可控的单机排序问题

研究带有学习效应和恶化效应的单机排序问题。在此模型中,工件的学习效应是与工件加工位置相关的减函数,工件的恶化效应是与其开始加工时间相关的线性函数。在无资源约束的情况下,分别讨论了目标函数为最大完工时间、总完工时间及总完工时间的绝对差之和的排序问题,证明了这些问题都是多项式时间可解的。对于带有资源约束问题,若分配一定的资源,工件加工时间会减少。讨论了在线性资源分配情况下,带有学习效应、恶化效应和资源分配量的交货期排序问题,其中所有工件有一个共同的交货期。目的是确定最优交货期、资源分配及工件的加工顺序,使交货期、提前、延误和资源分配量之和最小,通过将其转化为指派问题,证明问题是多项式时间可解的。     

带有准备时间和退化维护的单机排序问题

研究带有可变加工时间、准备时间和退化维护的公共交货期与凸资源分配的单机排序问题.工件的实际加工时间是关于所分配的不可再生资源量和与工件位置有关的退化效应的函数,并且在每个工件加工之前都有一个准备时间,它是有关资源分配的凸函数.为了消除机器的退化,在规划时间内最多允许执行一次维护活动.在资源总量有限的条件下,确定最优工件排序、最优公共交货期、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的总费用最小.根据优化的相关知识,将问题转化为匹配问题,给出了该问题的启发式算法.     

带有线性退化工件和退化维护时间的单机窗口排序

排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注。排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用。在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的。文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间;2)工期窗口的位置和大小;3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小。文章最后给出了这个问题的最优算法,其时间复杂性是O(n2logn)。     

带有可控性维护的单机调度问题研究

为在附加费用不大的条件下,通过最小化工件完成时间之和来减小work-in-process中的库存,尽可能使工件按期交付,在将工件调度与机器维护统一进行考虑的模型基础上,提出了带有预防性维护的单机调度问题,并对其进行了建模.将机器的维护周期适当放宽,以便在保证总的附加费用不超出预先给定的一个常数的前提下,实现工件的完成时间和的最小化.对工件加工允许中断的情况给出时间复杂度为O(n*ln(n));对工件加工不允许中断的情况给出一个启发式算法,其时间复杂度为O(n2).由该启发式算法很容易得到问题的可行解,从而为问题的进一步研究打下了基础.     

带有恶化和拒绝的工期指派的单机排序问题

讨论带有恶化和拒绝工件的工期指派的单机排序问题。工件的实际加工时间是其开始加工时间的线性增函数。如果工件被拒绝,则有一个惩罚费用,否则工件被加工。每个工件都要确定一个工期,文章讨论的工期指派分为CON(共同工期指派)和SLK(相同松弛工期指派)两种情况。对于CON工期指派问题,其目的是确定最优公共工期及工件的加工顺序,使工期、提前、延误和拒绝的总费用最小。将该问题归结为一系列指派问题,从而得到了一个复杂性为O(n4)的算法来求解此问题。对于SLK工期指派问题,目的是确定最优的松弛量及工件的加工顺序,使松弛、提前、延误和拒绝的总费用最小。将其归结为一系列指派问题,给出了求解此问题的多项式时间的最优算法。     

带有退化维护和退化工件的单机排序问题

对带有维护活动和工件退化的单机排序问题进行研究。机器需要在某一个时间段内进行维护以提高其加工速度,且在这段时间内机器不能加工任何工件。机器维护后恢复到初始状态,工件的退化效应重新开始,其中机器的维护时间是维护开始时间的线性非减函数,工件的实际加工时间是与其特定位置有关的退化函数。目标是找到机器的最优维护位置、极小化时间表长。对于单机情形,给出了最优排序的一些性质。在特定条件下,证明了最优排序与工件排序无关,最优维护活动排在给定排序的中间位置。     

具有共同松弛时间的恶化型工件排序问题研究

研究工件加工时间具有恶化效应的单机松弛工期排序问题.其中恶化效应指的是工件的实际加工时间是其开工时间的递增函数且所有工件的恶化率相同,工件的松弛工期等于其实际加工时间加上共同的松弛时间.目标是确定工件的一个排序和工件工期的共同松弛时间使得工件的提前时间、延迟时间和工期的共同松弛时间的线性加权和达到最小.用运筹学方法证明了该问题可以转化为两个向量的乘积问题,从而多项式时间可解,并给出了求解的最优算法.     

单机随机加工时间的交货期窗口设置

讨论n个独立工件在一台机器上加工，而且工件加工时间服从正态分布的交货期窗口设置问题，在等宽交货期窗口条件下，确定了工件交货期窗口，并证明这种交货期窗口设置只与窗口设置有关，而与工件排序无关。     

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

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

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

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