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

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

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

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

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

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

在退化维修下带有工期指派和加工时间可控的单机排序问题

讨论在一次退化维修下带有3种工期指派和加工时间可控的单机排序问题。其中机器的维修时间是维修开始时间的线性非减函数,工期指派的3种模型包括共同工期指派模型、松弛工期指派模型、无限制工期指派模型,工件的实际加工时间依赖于工件的开工时间、工件的位置以及资源分配的函数。目标是要找到机器的最优维修位置和最优排序,极小化提前时间、延误时间、工期以及资源分配的总费用。当机器的维修位置固定时,证明了该问题可以转化为指派问题;当机器的维修位置不固定时,给出了一个算法,并证明了该问题可以在O(n4)时间内求得最优解;最后以共同工期指派模型为例给出一个实例。     

资源约束下加工时间可变的工期窗口指派问题

研究单机排序下加工时间可变的工期窗口指派问题,任务的加工时间是关于所获资源分配量的一个凸函数,同时也考虑了学习、退化效应对任务加工时间的影响,即任务的实际加工时间依赖于该任务的加工位置和开始加工时间以及分配到该任务的资源量。每个任务都有一个独立的工期窗口,但所有任务的工期窗口宽度相同。目标是确定最优的工期窗口开始时间、工期窗口宽度、最优的资源分配量以及最优的任务排序。最小化提前、误工工件惩罚、工期窗口开始时间、工期窗口宽度、资源分配以及最大完工时间的总费用。证明了此问题是多项式时间可解的,并给出了最优算法。     

具有截断控制参数学习效应的单机排序问题

讨论具有截断控制参数学习效应和退化效应且工件的加工时间依赖于资源分配的单机排序问题。分别在线性资源和凸资源消费函数条件下研究问题。每个任务有一个松弛工期窗口,任务的实际加工时间依赖于截断控制参数、工件的开始加工时间和分配方案的资源数量。目标是求出任务的最优排序、每个任务的工期窗口位置、最优资源分配,使由任务总提前、延误、工期窗口的开始时间、窗口大小、时间表长、总完工时间及资源总费用的加权和最小。将问题转化为指派问题,证明了该问题是在多项式时间内可解的,并分别给出了2个多项式时间的最优算法。     

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

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

带有学习效应和退化效应的可拒绝排序问题

讨论了具有学习效应和退化效应的多窗口的可拒绝单机排序问题。工件的实际加工时间与开始加工时间和所排位置有关。工件集分为接受工件集和拒绝工件集,对于被拒绝加工的工件而言,它的费用只与工件有关,目标是确定接受工件集的最优加工顺序和拒绝费用,从而极小化2个费用函数。考虑2个问题,第1个问题的目标函数是与提前、延误、窗口的开始时间、窗口的大小以及拒绝费用有关的函数,第2个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小以及拒绝费用有关的函数,并且针对这2个问题分别给出了多项式时间算法。     

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

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

带有学习效应的加工时间可控退化工件单机排序问题

讨论了带有学习效应、加工时间可控的退化工件的单机排序问题。工件的实际加工时间是一个关于所排位置、开始加工时间和所分配资源的函数。加工时间可控是指工件的实际加工时间是一个依赖资源分配量的函数。目标是确定工件的最优排序、最优加工时间和最优资源分配量、极小化最大完工时间、总完工时间、完工时间差和资源消耗的总费用。考虑了2种情形:学习因子与工件有关的线性资源函数;将学习效应与工件的实际加工时间、依赖开始时间结合在一起的凸资源函数。通过分析最优解的一些重要性质,将这2个问题分别转化为指派问题,给出了2个计算复杂性为O(n3)的最优算法,证明了该问题是多项式时间可解的。     

带有退化效应和不可用区间的并行批排序问题

在制造业中,处理机由于长时间使用而发生故障或进行维护、保养等原因,产生一些不可用区间;并且工件的实际加工时间往往与它的开始加工时间有关。研究一种带有退化效应和不可用区间的无界单机并行批处理机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数。而并行批处理机中,同批工件同时开始加工,同时完工,且批一旦开始加工就不可中断;每批的加工时间等于这批工件中加工时间的最大者;同批中工件的完工时间都相同,为这批的完工时间。讨论的目标函数为最大完工时间问题。通过对最优解性质的分析,给出了求解此问题的多项式时间的最优算法。     

带有维修活动和工件可拒绝的单机排序问题

讨论了带有交货期、维修活动和工件可拒绝的单机排序问题,这一问题是将所有的工件分成2个集合,分别是被接受的工件集和被拒绝的工件集。规定每个被接受的工件都有一个待定的交货期,且所有工件的交货期的大小相同。如果工件在交货期内完工,则不产生任何费用,否则工件提前或延误,会产生相应的提前或延误的费用。而对于拒绝工件而言,它的费用只与工件有关。维修活动需要在一个固定的时间长度内完成,排在维修活动之后的工件的加工时间将会减少。这类问题的总费用是2个工件集的费用之和,目标函数是确定被接受工件的最优排序,极小化接受工件和拒绝工件的总费用,该问题在多项式时间可解,在今后的应用中能发挥作用。     

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

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

带有学习效应和加工时间可控的排序问题

考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。     

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

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

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

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

带不可用时间段和恶化加工时间的几个多项式可解问题

文章研究了机器带有一个不可用时间段并且加工时间恶化的单机调度问题,考虑了2种不同加工时间函数下的2种目标函数;首先讨论了机器一直可用的情况,证明了2个带恶化加工时间的问题是多项式可解的,在此基础上对机器带一个不可用时间段时的情况进行了讨论,证明了这2种约束下的几个问题的多项式可解性.     

加工时间恶化的单机成组排序问题

讨论了一类在成组技术条件下，工件的加工时间恶化的单机排序问题。工件的加工时间是开工时间的线性函数，同时工件组的安装时间也是开始安装时刻的线性函数，同组工件间必须连续加工且没有安装时间，不同组工件间连续加工时有安装时间。基于对问题的分析，给出了多项式算法。     

Scheduling Step-Deteriorating Jobs on Parallel Machines by Mixed Integer Programming

Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.