最小化最大加权完工时间重新排序研究

重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是:1)在原始排序错位限制的条件下最小化最大加权完工时间;2)最小化最大加权完工时间与原始排序的错位的加权和.在本文研究中我们假设所有工件在0时刻到达.文章的主要结果:对于Γ∈{D_(max)(π~*),△_(max)(π~*)},给出了问题1|Γ≤k|max w_jC_j和问题1‖maxw_jC_j+μΓ多项式时间的求解算法;证明了问题1|∑△_j(π~*)≤k|max w_jC_j和问题1‖max w_jC_j+μ∑△_j(π~*)是强NP-困难的.     

具有错位限制且工件可退化的单机重新排序问题

重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达,新工件的安排使得原始工件重新排序而产生错位.考虑了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题.工件的位置错位和时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化最大延迟问题.其中退化效应是指其实际加工时间是开工时间的非减函数,工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差,工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差.对以上两类问题,当权重系数或者错位限制满足特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列,基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法.     

序列错位限制下最小化完工时间和的继列分批重新排序

在单机分批排序中,一个原始工件集已经分好批排好顺序,使得给定的目标函数最小.当一个新的工件集到来时,决策者需要插入这些新工件到原来的顺序中,这样使得原始工件就会产生一些错位.但为了满足对原始工件集的要求而不过分的打乱它们的顺序的条件下,使得新的目标值为最优.本文主要研究的是在序列错位量限制的条件下,继列分批最小化总完工时间的重新排序问题,对于最大序列错位和总序列错位的不同约束情况下,研究可行排序和最优排序的结构性质,进而设计了它们的多项式时间算法.     

具有指数和位置学习效应的机器排序问题

本文考虑指数学习效应和位置学习效应同时发生的新的排序模型.工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置.单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法.此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法.流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法.     

带强制工期的可中断单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.     

带强制工期的可中断平行机排序问题

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.     

极小化最大提前完工时间的两平行机排序问题

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.     

具有学习和退化效应的单机干扰管理问题

针对工件同时具有学习和退化效应、机器具有可用性限制这一问题,建立可预见性单机干扰管理模型。在这一模型中,工件的加工时间是既与工件所排的加工位置又与工件开始加工的时间有关的函数。同时,在生产过程中由于机器发生故障或定期维修等扰动事件导致机器在某段时间内不能加工工件。目标是在同时考虑原目标函数和由扰动造成的偏离函数的情况下,构建一个新的最优时间表序列。根据干扰度量函数的不同研究了两个问题,第一个问题的目标函数是极小化总完工时间与总误工时间的加权和;第二个问题的目标函数是极小化总完工时间与总提前时间的加权和。对于所研究的问题,首先证明了最优排序具有的性质,然后建立了相应的拟多项式时间动态规划算法。     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

带有退化效应和序列相关运输时间的排序问题

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.     

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。     

带折扣因子的单机干扰管理研究

针对可预见的干扰管理问题,考虑单机环境下,加权折扣最短加工时间优先(WDSPT)序为原目标的最优加工次序,研究了如何对初始加工时间表进行修改。在干扰事件影响下,初始加工时间表将不再是最优,甚至不再可行。和大多数重排序研究不同,构建了同时考虑原目标和由干扰事件造成的扰动目标的重排序模型,并基于理想点法提出一种动态规划算法来求解所建模型中的双目标排序问题。最后通过一个数值算例来说明该重调度模型对于求解带折扣因子的单机干扰管理问题是有效的。     

工件延误和可拒绝下的单机重新排序问题的近似方案

研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题.在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定.然而,在工件正式开始加...     

相容工件系统的最小化最大延迟与误工和的重新排序

在单机重新排序问题中,一个原始工件集已经排好顺序,使得给定的目标函数最小．当一个新的工件集到来时就会产生一些错位,决策者需要插入新工件到原来排序中而还不能过分打乱它们的顺序．该论文首先研究了当工件加工时间和工期相容时,在错位量限制的条件下最小化最大延迟问题;也研究了当工件加工时间相同或工件工期相同时,在错位量限制的条件下最小化误工和问题．对这些问题,给出了好的算法．     

The dynamic vehicle rescheduling problem

The pre-planned schedules of a transportation company are often disrupted by unforeseen events. As a result of a disruption, a new schedule has to be produced as soon as possible. This process is called the vehicle rescheduling problem, which aims to solve a single disruption and restore the order of transportation. However, there are multiple disruptions happening over a “planning unit” (usually a day), and all of them have to be addressed to achieve a final feasible schedule. From an operations management point of view the quality of the final solution has to be measured by the combined quality of every change over the horizon of the “planning unit”, not by evaluating the solution of each disruption as a separate problem. The problem of finding an optimal solution where all disruptions of a “planning unit” are addressed will be introduced as the dynamic vehicle rescheduling problem (DVRSP). The disruptions of the DVRSP arrive in an online manner, but giving an optimal final schedule for the “planning unit” would mean knowing all information in advance. This is not possible in a real-life scenario, which means that heuristic solution methods have to be considered. In this paper, we present a recursive and a local search algorithm to solve the DVRSP. In order to measure the quality of the solutions given by the heuristics, we introduce the so-called quasi-static DVRSP, a theoretical problem where all the disruptions are known in advance. We give two mathematical models for this quasi-static problem, and use their optimal solutions to evaluate the quality of our heuristic results. The heuristic methods for the dynamic problem are tested on different random instances.     

Predictive–reactive scheduling on a single resource with uncertain future jobs

We consider a scheduling problem where the firm must compete with other firms to win future jobs. Uncertainty arises as a result of incomplete information about whether the firm will win future jobs at the time the firm must create a predictive (planned) schedule. In the predictive schedule, the firm must determine the amount of planned idle time for uncertain jobs and their positions in the schedule. When the planned idle time does not match the actual requirements, certain schedule disruptions occur. The firm seeks to minimize the sum of expected tardiness cost, schedule disruption cost, and wasted idle time cost. For the special case of a single uncertain job, we provide a simple algorithm for the optimal planned idle time and the best reactive method for schedule disruptions. For the case of multiple uncertain jobs, a heuristic dynamic programming approach is presented.