混合无等待流水线干扰管理调度方法研究

针对带分批约束的混合无等待流水加工环境中干扰事件的出现导致初始调度计划发生偏离的问题,研究如何运用干扰管理理论来应对工件变更扰动情况,建立了兼顾最小化工件完工时间加权和指标(初始调度目标)和最小化工件完工滞后时间加权和指标(偏离校正目标)的干扰管理调度模型,提出了双层微粒群优化策略与随机多邻域搜索机制相结合的混合求解算法。数值算例仿真实验结果表明,包含“插入-交换”大概率邻域搜索算子的混合微粒群优化算法求解本文所构建的干扰管理调度模型是有效的。     

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

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

考虑加工效率变化的变速机干扰管理研究

在变速机生产排序中, 受来自企业外部可改变机器加工效率的突发性干扰事件影响, 初始最小化企业生产成本的加工时间表不再最优,需要对其调整并在生产成本和干扰事件扰动之间进行权衡。建立了同时考虑生产成本和干扰事件扰动的重排序模型, 生产成本为所有机器的负载之和, 干扰事件的扰动为工件在不同机器之间重新安排所产生的运输费用和。设计了求解该重排序问题有效前沿的算法, 以及利用决策者对两个目标的偏好将双目标转化成一个二元非线性函数后, 求解优化该函数的有效解的算法。通过数值算例验证与整个有效前沿相比,优化二元函数的算法只需搜索部分有效前沿即可求出最优解,降低了有效解的搜索比例和运行时间,提高了干扰管理问题的处理效率。     

行驶时间延迟下物流配送干扰管理模型——基于客户终身价值的视角

物流配送过程中干扰事件导致行驶时间延迟后,初始配送方案将不再最优甚至根本不可行,此时如何生成副作用最小的调整方案,快速恢复配送的正常运行,是当前研究的难点。本文首先将客户为企业当前(及潜在)贡献价值考虑在内,基于客户终身价值对系统扰动进行度量。进而兼顾偏离成本和初始目标,构建干扰管理模型并提出相应的启发式算法。算例结果表明:与其他重调度方法相比,本文方法的实用性更强。     

考虑加工速率相互干扰的平行机调度最优策略研究

随着智能互联网的应用深入、个性化消费时代的来临,制造服务企业开始注重利用网络平台为客户提供个性化的定制服务,在此过程中派生出了产品设计师可与多名客户在线同步交互的一种新型服务模式。本文根据设计师服务效率受并行服务客户数量影响的特征,将问题刻画为机器处理速度相互影响的一类平行机调度模型,以最小化总完工时间为优化目标,研究设计最优调度方案。首先,对于只有两名设计师且各自同时处理最多两个任务的情形,提出了改进的SPT调度规则,运用归纳法证明了该规则可以生成最优加工方案。其次,对改进的SPT规则进行任务分配方式的适当松驰以便更加易于操作,并证明松驰后的新分配方案保持了解的最优性。最后,将相关结论推广至多名设计师的一般情形。上述研究为个性化在线定制服务模式下的有效调度策略制定提供了良好的理论支撑。     

有顾客需求变动的车辆调度干扰管理研究

为解决来自顾客需求变动所引发的物流配送干扰问题,提出基于干扰管理思想构建扰动恢复策略与方案.应用虚拟单车场实现了车辆调度扰动恢复问题转化,提出了车辆调度扰动恢复策略以及扰动度量方法,以作为车辆调度干扰管理建模的基础;对有顾客需求变动的车辆调度干扰管理问题,分析了顾客需求变动造成的扰动并进行了辨识;建立了相应的干扰管理模型,并提出了归一化处理办法对VRPTW问题进行有效兼容;结合干扰管理模型的特点,改进了基于顾客的编码表示方法;根据干扰管理思想,设计了遗传算法对干扰管理模型进行了求解.最后通过实验验证了模型与算法的有效性.     

考虑成本的最大延迟时间同类机调度问题

假定生产时机器成本是固定的,研究了一类考虑成本的同类机调度问题,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。为该类问题构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法H,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。     

基于混沌量子算法和MAGTD的多目标FJSP求解策略

针对多目标环境下柔性作业车间的调度问题,以最小化最大完工时间和惩罚值为目标,建立调度问题的数学模型,提出了基于混沌理论的量子粒子群算法。针对实际生产交货期不确定的特点,在量子粒子群算法基础上,提出引入混沌机制建立初始群的方法;利用混沌机制的遍历性,提出混沌局部优化策略;为获取最优调度方案提出了引入多指标加权灰靶选择策略。通过典型基准算例和对比测试,验证了所提出的算法获得最满意调度方案的可行性和求解多目标柔性作业车间调度问题的有效性。     

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

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

考虑路径冲突的AGV配置与调度优化

合理调度有限的码头资源以满足船舶的装卸时间要求是自动化集装箱码头的重要目标之一。针对自动化集装箱码头自动导引车(automated guided vehicle,AGV)配置与调度问题,考虑船舶装卸时间要求和AGV运输过程中的路径冲突,提出分阶段调度策略。将船舶装卸作业分为卸船阶段、装卸同步阶段、装船阶段三个阶段,在每个阶段中,建立以最小化最大完工时间和最小化AGV空载和等待时间为双目标的调度优化模型,并设计基于NSGA-Ⅱ的启发式算法求解。根据本阶段的实际完工时间,从最优解集中选择下一阶段AGV的配置与调度方案。最后对比其他调度方案表明本文调度方案能够满足集装箱船的装卸时间要求,且提高了AGV的利用率,更符合码头实际作业要求。     

单机排序中关于完工前总损失的应急管理

该文研究了扰动环境下的关于完工前总损失的单机排序问题, 也就是这样一个问题: 在时刻 t , 一部分工件已经完工了, 一个扰动发生了, 在这种情形下, 原来的排序已经不是最优排序甚至是不可行排序了. 因此就需要对未完成的工件找一个新的排序. 作者采用的方法与大多数重新排序问题所不同的是: 模型里包含了原始排序与新排序之间的偏差所造成的损失. 作者主要研究了在原始排序中加权最短加工时间规则(WSPT)是最优排序的情形. 根据扰动的类型, 应急管理策略的类型以及目标函数, 研究了几个问题. 对于每个问题, 作者找到了最优排序或者得出了一些重要结果.     

Some single-machine scheduling problems with actual time and position dependent learning effects

In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively.     

Single-machine total completion time scheduling with a time-dependent deterioration

In this paper, we consider the single-machine scheduling problems with a time-dependent deterioration. By the time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total completion time. We develop a mixed integer programming formulation for the problem. The complexity status of this problem remains open. Hence, we use the smallest normal processing time (SPT) first rule as a heuristic algorithm for the general cases and analyze its worst-case error bound. Two heuristic algorithms utilize the V-shaped property are also proposed to solve the problem. Computational results are presented to evaluate the performance of the proposed algorithms.     

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

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

SPT optimality (mostly) via linear programming

One of the oldest results in scheduling theory is that the Shortest Processing Time (SPT) rule finds an optimal solution to the problem of scheduling jobs on identical parallel machines to minimize average job completion times. We present a new proof of correctness of SPT based on linear programming (LP). Our proof relies on a generalization of a single-machine result that yields an equivalence between two scheduling problems. We first identify and solve an appropriate variant of our problem, then map its solutions to solutions for our original problem to establish SPT optimality. Geometric insights used therein may find further uses; we demonstrate two applications of the same principle in generalized settings.     

Two new algorithms for solving optimization problems with one linear objective function and finitely many constraints of fuzzy relation inequalities

This paper studies the optimization model of a linear objective function subject to a system of fuzzy relation inequalities (FRI) with the max-Einstein composition operator. If its feasible domain is non-empty, then we show that its feasible solution set is completely determined by a maximum solution and a finite number of minimal solutions. Also, an efficient algorithm is proposed to solve the model based on the structure of FRI path, the concept of partial solution, and the branch-and-bound approach. The algorithm finds an optimal solution of the model without explicitly generating all the minimal solutions. Some sufficient conditions are given that under them, some of the optimal components of the model are directly determined. Some procedures are presented to reduce the search domain of an optimal solution of the original problem based on the conditions. Then the reduced domain is decomposed (if possible) into several sub-domains with smaller dimensions that finding the components of the optimal solution in each sub-domain is very easy. In order to obtain an optimal solution of the original problem, we propose another more efficient algorithm which combines the first algorithm, these procedures, and the decomposition method. Furthermore, sufficient conditions are suggested that under them, the problem has a unique optimal solution. Also, a comparison between the recently proposed algorithm and the known ones will be made.