一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

安装时间与次序相关的生产调度干扰管理研究

在安装时间和次序相关的单机调度问题中,为应对突发性的工件优先级变动造成的影响,构建了双目标重调度模型。原目标为生产的流程时间,扰动目标为工件的加工次序扰动。针对模型中的双目标,设计了基于有效解的两阶段混合启发式算法进行求解,在原目标和扰动目标之间进行权衡。混合算法第一阶段里,基于任意单个工件次序变化将双目标问题转化成单目标TSP问题,利用最近邻域和插入混合求得单目标问题的若干解,构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势,对初始种群进行扩展搜索,最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标,验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

分时电价下关注能耗成本的生产问题建模及算法

随着环境保护及能源危机问题的日益突出,如何均衡用电负荷、适应能源供给侧结构特点,从而减小企业运营成本以提高自身盈利能力,已经成为能源敏感型企业在当前时代亟待解决的实际问题。本文以单机生产系统为研究对象,建立了分时电价模式下能耗成本最小化问题的连续时间混合整数规划模型。首先,针对工件顺序固定时的子问题,考虑到非线性因素的影响,证明了最优缓冲时间长度与电价调整时刻的一致性关系,据此设计了分枝定界算法中的分枝规则,并通过开发快速的低界求解方法及有效的剪枝策略,保证了算法可在短时间内求得精确解。继而,通过随机排序、ERD排序、邻域搜索排序、遗传算法排序等不同方法的比较,分析了工件顺序对问题最终总成本的影响程度。同时,在不同参数组合的数据实验中,将本方案与传统生产调度方案进行对比,表明了本文模型在节约能耗成本方面的巨大优势。最后,本文所设计算法解决了周期差异引起的非线性的难题,可以此为子模块求解更加复杂的扩展问题,比如考虑可再生能源生产周期的企业内多种能源实时分配问题。     

多油品供给受限下多油库被动配送车辆路径问题研究

成品油供给不足将导致加油站油品订单无法完全满足,如何安排有限油品的合理配送对保障能源供给安全至关重要。为此,本文考虑有限供给下不同客户配送的优先次序,开展配送计划、车辆调度和路径优化等油品配送网络规划活动,对多油品供给受限情况下多油库被动配送车辆路径问题（Multiple Depot Vehicle Routing Problem,MDVRP）进行深入研究。首先,文章构建了考虑需求优先等级和配送成本的多油品多油库车辆路径规划多目标优化模型。其次,采用多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization,MOPSO）对模型进行求解,以实现车辆高效调度和油品配送路径优化。最后,基于CNPC在青岛市部分油库和加油站点的数据信息,构建油品配送网络进行实证检验。算例结果显示,配送车辆路径经过优化后,生成Pareto非劣解集,配送成本显著降低,配送满足率明显提高,这也进一步验证了该模型及相关算法的可行性和有效性。     

基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

时间窗口约束下基于改进蚁群算法的协同制造调度研究

与传统调度模式不同，协同制造模式下企业之间的调度模式极其复杂。协同企业间的加工工序路线并不固定，且不同类型产品具有不同的加工路线网络。为此本文针对平衡型、瓶颈型、跳跃型、混合型四类具有典型特点的协同制造网络G_p进行分析和设计；考虑制造企业同类产品合并加工策略，构建基于连续加工量的分段生产成本函数；通过设计合理的订单最早交货时间和最晚交货时间，对订单交货进行时间窗口约束，并在此基础上构建了由制造商生产成本W_c^m、订单等待W_s^k（Q_k， T'_k）和提前完工库存成本W_s^k（Q_k， T″_k）、延期惩罚成本构成W_l^k（Q_k， T'″_k）的目标函数。为求解该模型，创新性将蒙特卡洛思想引入蚁群算法，提高蚂蚁选择合理性，避免局部最优；同时，采用移动窗口[min， max]奖励机制，并且对信息素奖励乘以平衡系数k（N）提高奖励可信度，加快搜索速度并提高求解性能。仿真结果表明，本文构建调度模型合理，可以获得优化的调度结果；同时，本文提出的蚁群改进寻优算法具有良好的求解速度和收敛性，算法具有较好的稳定性。     

一类应急物资调度的双层规划模型及其算法

应急物资的调度是应急管理中的一个重要分支,衡量其运作效果的两个最常用的指标是应急时间和应急成本,目前的建模大多都以多目标规划为主.但现实告诉我们,面对应急事件,应该在最短的允许时间奔赴现场,而成本与此目标相比要次之.为此,建立了单资源应急物资调度的双层规划模型,上层为时间目标,下层为成本目标,并将此模型的求解转化为若干个有限制的运输问题的求解,利于计算机实现.算例证明了算法的有效性.     

国家血液战略储备库选址——库存问题

建立血液战略储备库是应对大规模突发事件应急血液保障问题的重要途径之一.为提高应急血液保障能力,以灾后应急血液保障时效性最高及日常条件下血液战略储备库运营总成本最低为目标,基于非线性混合整数规划方法建立了一个考虑多情景、多阶段、多血型、随机需求、库存补充提前期、容量限制及协同定位等因素的血液战略储备库多目标选址—库存问题优化模型.根据该模型的性质,设计了一种基于小生境技术的多目标非支配排序遗传算法进行求解.算例分析结果表明,该算法能够有效获得Pareto前沿,产生一簇Pareto解,因而决策者可根据偏好与实际需要权衡应急血液保障成本与时效性,选择合适的血液战略储备库选址—库存决策方案.     

聚类视角下的差异工件平行机批调度问题

从聚类角度研究差异工件批调度这一组合优化问题.论证了差异工件的分批问题实质为一种广义聚类问题,为求解批调度问题提供了一个全新的途径.提出了批的空间浪费比的概念,将最小化批的总加工时间目标变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明.此外,以批的空间浪费比为基...     

A coordination mechanism for a scheduling game with parallel-batching machines

In this paper we consider the scheduling problem with parallel-batching machines from a game theoretic perspective. There are m parallel-batching machines each of which can handle up to b jobs simultaneously as a batch. The processing time of a batch is the time required for processing the longest job in the batch, and all the jobs in a batch start and complete at the same time. There are n jobs. Each job is owned by a rational and selfish agent and its individual cost is the completion time of its job. The social cost is the largest completion time over all jobs, the makespan. We design a coordination mechanism for the scheduling game problem. We discuss the existence of pure Nash Equilibria and offer upper and lower bounds on the price of anarchy of the coordination mechanism. We show that the mechanism has a price of anarchy no more than \(2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}\).     

Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart

We consider the online scheduling of equal length jobs on unbounded parallel batch processing machines to minimize makespan with limited restart. In the problem \(m\) identical unbounded parallel batch processing machines are available to process the equal length jobs arriving over time. The processing batches are allowed limited restart. Here, “restart” means that a running task may be interrupted, losing all the work done on it, and the jobs in the interrupted task are then released and become independently unscheduled jobs, called restarted jobs. “Limited restart” means that only a running batch that contains no restarted jobs can be restarted. For this problem, we present a best possible online algorithm.     

Scheduling a single semi-continuous batching machine

This paper addresses a new problem, called semi-continuous batch scheduling, which arises in the heating-operation of tube-billets in the steel industry. Each heating furnace can be regarded as a semi-continuous batching machine, which can handle up to C jobs simultaneously. The jobs in the same batch enter and leave the machine semi-continuously, which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time. In this paper the processing time of a batch depends on the capacity of the semi-continuous batching machine, the longest processing time of jobs in the batch and its size. The objectives are to schedule jobs on the machine so that the makespan and the total completion time are minimized. A schedule for a semi-continuous batching machine consists of a batching and sequencing for the batches. We propose the optimal properties of two different objective functions and present the different dynamic programming algorithms with a running time of O(n²), respectively.     

大规模集成电路预烧作业中分批排序问题的数学模型

分批排序(Batch Scheduling)是在半导体生产过程的最后阶段提炼出来的一类重要的排序问题。单机分批排序问题就是n个工件在一台机器上加工,要将工件分批,每批最多可以同时加工B个工件,每批的加工时间等于此批工件中的最大的加工时间。Skutella^[8]1998年把平行机排序的P｜｜∑ω_jC_j和R｜｜∑ω_jC_j表述成二次的0-1整数规划,得到一些令人满意的结果;国内罗守成等^[9]、张倩^[10]给出了单机排序问题1｜｜∑ω_jC_j的数学规划表示,对于用数学规划来研究排序问题是一个很有意义的进展。本文首先介绍总完工时间和最小的带权单机分批排序问题1｜B｜∑ω_jC_j,然后将1｜B｜∑ω_jC_j表示成数学规划的形式,并且用数学规划中的对偶理论证明了SPT序是其特殊情况1｜B=1｜∑C_j的最优解。     

Scheduling in an assembly-type production chain with batch transfer

This paper addresses a three-machine assembly-type flowshop scheduling problem, which frequently arises from manufacturing process management as well as from supply chain management. Machines one and two are arranged in parallel for producing component parts individually, and machine three is an assembly line arranged as the second stage of a flowshop for processing the component parts in batches. Whenever a batch is formed on the second-stage machine, a constant setup time is required. The objective is to minimize the makespan. In this study we establish the strong NP-hardness of the problem for the case where all the jobs have the same processing time on the second-stage machine. We then explore a useful property, based upon which a special case can be optimally solved in polynomial time. We also study several heuristic algorithms to generate quality approximate solutions for the general problem. Computational experiments are conducted to evaluate the effectiveness of the algorithms.     

Processing in a multi-machine batch manufacturing system with sequence dependent cost

Many workcells in batch manufacturing systems are populated with multiple, nonidentical machines that perform similar tasks. Because of the size of a batch when a job arrives, it may be uneconomical to set up two or more machines to process the same job simultaneously. An economic decision has to be made as regards which machine in the cell to assign the job. Likewise, many multi-operation jobs can be processed using one of several feasible operation sequences that may lead to different total manufacturing costs. The cost differences are the result of several factors, among which are processing time and cost dependencies between operations, fixturing requirements, and material handling requirements. When the workcell machine selection decision is considered along with the operation sequencing decision, determination of the best machine in a cell and the best operation sequence for the batch is a non-trivial task. In this paper, we address the problem of selecting the best machine within a cell and the best operation sequence for a batch when operation cost is machine and sequence dependent. The problem is modeled mathematically and solved using a heuristic algorithm. The performance of the algorithm is compared with that of an exact solution procedure.     

Online integrated production–distribution scheduling problems without preemption

We study an integrated production–distribution scheduling problem where jobs are released by customers to a manufacturer over time. The jobs are released online, that is, at any time the information of the number, release and processing times of future jobs is unknown, and the processing time of a job becomes known when the job is released. The manufacturer processes the jobs on a single machine. During the processing of jobs preemption is not allowed. Completed jobs are delivered in batches to customers via sufficient capacitated vehicles. For the objective of minimizing the sum of the total delivery time and the total distribution cost, we present a 3-competitive algorithm for the single-customer case and then extend the result to the multi-customer case. A lower bound of two on the competitive ratio of the problem is also given.     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.