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

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

带有退化工件和机器维修区间的单机排序问题

考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚;如果被加工,那么工件被排在机器上(机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件)进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP-难的。     

工件带运输时间的单机分批排序问题

主要考虑了在线和离线两种模型下的工件带运输时间的单机分批排序问题.工件一但被加工完将会被马上运往目的地.我们考虑了三种限制模型:(1)在线模型:批量B无穷大,工件的加工时间和运输时间一致,即:若工件Ji的加工时间Pi大于等于工件Jj的加工时间pj,那么它们的运输时间有qi≥qj.(2)在线模型:批量B无穷大,工件的最大运输时间和最小的运输时间的比小于等于1 平方根5/2.对于(1),(2)这两种模型我们给出了一个竞争比为1 平方根5/2的在线算法,并且这个结果是最好的.(3)离线模型:批量B有限,当工件的到达时间是整数并且加工时间P=1时,我们给出了一个时间复杂性为O(n2lnn)的多项式时间算法,当工件的加工时间不是1,但工件的到达时间的个数是一个常数m时,我们给出了一个时间复杂性为O(2m-1nlnn)的多项式时间算法.     

退化工件误工数的双机自由作业排序问题

探讨退化工件两台机器自由作业环境下的最小化加权误工工件的排序问题,其中所有工件具有相同的公共交货期。首先证明了最小化误工工件数问题是 NP 困难的;然后对最小化加权误工工件数问题给出了一个拟多项式时间算法;最后对几种特殊情形给出了多项式时间算法。     

应用遗传算法进行单机工件加工排序

运用遗传算法和提前／拖期调度模型，研究了在单机情况下工件加工排序问题，提出了一个新算法，此外，在应用遗传算法的过程中，还提出了“二次编码”的方法和利用ＥＤＤ法则作为寻找最优排序起始眯的思想，从而加快了新算法的收敛速度。     

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

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

极小化延误工件个数的单机分组排序问题

研究了以极小化延误工件个数为目标的单机分组排序问题，证明了该问题是强ＮＰ困难的，甚至限定所有工件有单位加工时间和一致的组间调整时间也是如此。     

带有退化工件和拒绝的不同类型机排序问题

在工业生产过程中,由于一些特殊的原因,工件可以被拒绝加工但要付出相应的费用,即拒绝惩罚。为了节约处理成本,加工时间长的工件或者加工所需的费用高的工件,可以支付一定的费用来进行外加工或购买。将退化和拒绝结合起来考虑,讨论带有退化工件和拒绝的不同类型机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数,其中工件的退化率只与机器有关,与工件本身无关。目标函数是极小化接受工件的排序指标与拒绝工件总惩罚之和。排序指标分别为总时间表长和总完工时间。目的是找到拒绝工件集和接受工件集,并安排接受工件的加工顺序,使所求问题的目标函数值最小。通过将2个问题的目标函数转化为指派问题,证明了他们都是多项式可解的。     

退化工件2台机器异序车间作业排序问题

：文章讨论退化工件2台机器异序车间作业排序问题。在异序车间作业环境中,每个工件由一些工序组成,工序的个数未必与机器数相同。此外,每个工件有各自的工序加工顺序。工件可能多次在某些机器上加工,也可能根本不在某些机器上加工。假设工件的实际加工时间是其开始时间的比例函数,目标函数是极小化最大完工时间。首先证明了具有任意工序的问题是强意义下NP-难的;然后对每个工件最多只有2个工序的问题给出了多项式算法;最后证明了只有2个工序具有准备时间或截止工期的问题是普通意义NP-难的。     

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

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

带有退化、拒绝和不可用区间的单机排序问题

【目的】考虑带有退化工件、拒绝和不可用区间的单机排序问题。【方法】假设工件有不同的基本加工时间和相同的退化率,工件可以被拒绝,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件不可恢复。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。【结果】对于这个NP-难问题,在不可用区间前、后,工件按照基本加工时间a_j的非减顺序排列可以得到最优解,给出一个拟多项式时间动态规划算法和一个完全多项式时间近似策略。【结论】推广了已有文献的模型。     

具有交货时间的单机作业调度问题的最优解

基于回溯思想的算法通过系统地搜索解空间可以得到具有交货时间的n个作业的单机作业调度问题的最优解.给出一种改进算法,使得算法的时间复杂度由O(n!)降低到O(nlgn).     

Minimizing Tardy Jobs in a Single Machine Scheduling Problem with Fuzzy Processing Times and Due Dates

IntroductionThere are many scheduling problems of practicalinterest in which the input data are uncertain or i mprecise,and this kind of uncertainty or i mprecision cannot bedescribed by probability theory.For these situations wherecharacteristics and constraints are neither deter ministic norprobabilistic,the problems may often be modeled withfuzzy sets.Fuzzy logic,which was introduced by Zadeh[1]hasbeen appliedto various industrial problems including productionsystems[2,3].Recently,there ha…     

锁定初始调度的紧急工作单机重调度问题

对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(reschedulingrushjobswithloadslockedonsinglemachine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.     

最大化接收工件总权值的批处理机在线排序

研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p0,一个到达时间r_j≥0,一个权值w_j0,一个必须交货期d_j0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m~2-m)~(1/2)/(2m~2-m).     

恶化工件具有p-s-d安装时间的非同类机排序

主要讨论了恶化工件具有p-s-d安装时间的非同类机排序问题.工件的实际加工时间与开工时间有关,安装时间是依赖于所在机器上已加工完的工件的加工时间的简单函数,即p-s-d形式.本文所考虑的问题是如何确定工件在非同类机上的加工顺序使得所有工件的总完工时间最小.在每台机器上加工的工件数确定的情况下,将该排序问题转化为一个指派...     

并行多机成组工件调度的启发式算法

N个成组工件将在M台并行一致的机器上加工,当一个工件接在不同组的工件之后时需要装设,而接在同组工件之后时不需要重新装设,目标函数是使总的通过时间最小·利用最优解的必要条件,将单个工件组成基本运行,在研究基本运行组合规则的基础上,提出了一个基于基本运行的并行多机成组工件调度的启发式算法·在中、小规模水平问题上,将启发式算法的结果与最优解的结果进行了比较·效果令人满意·实验证明该启发式算法能够有效地解决成组工件调度的实际问题,具有解决中大规模实际问题的潜力·     

工件相同且发送批数受限的供应链排序问题

工件完工后成批发送的供应链排序问题是从实际生产中提炼出来的,针对发送批数受限制,最小化生产费用及发送费用的情况,当工件的权重与加工时间均相等时,生产费用是关于发送批数的单调递减函数,进而根据二分搜索法可以得到最优的发送批数。因此问题是多项式时间可解的。