A genetic algorithm application using fuzzy processing times in non-identical parallel machine scheduling problem

There are many scheduling problems which are NP-hard in the literature. Several heuristics and dispatching rules are proposed to solve such hard combinatorial optimization problems. Genetic algorithms (GA) have shown great advantages in solving the combinatorial optimization problems in view of its characteristic that has high efficiency and that is fit for practical application [1]. Two different scale numerical examples demonstrate the genetic algorithm proposed is efficient and fit for larger scale identical parallel machine scheduling problem for minimizing the makespan. But, even though it is a common problem in the industry, only a small number of studies deal with non-identical parallel machines. In this article, a kind of genetic algorithm based on machine code for minimizing the processing times in non-identical machine scheduling problem is presented. Also triangular fuzzy processing times are used in order to adapt the GA to non-identical parallel machine scheduling problem in the paper. Fuzzy systems are excellent tools for representing heuristic, commonsense rules. That is why we try to use fuzzy systems in this study.     

设备带有恶化特性的作业车间调度模型与算法

考虑到现实作业车间调度中设备具有恶化特性,针对作业的处理时间是开始时间的线性递增函数的作业车间调度问题, 建立了以最小化最迟完成时间为目标的优化模型,进而设计了嵌套分割算法进行求解.该算法在抽样阶段嵌入单亲遗传算法以提高抽样的多样性和质量. 实例结果表明,所提出的算法在解决该问题上可以获得较高质量的解,并且具有很好的鲁棒性.     

求解多目标job-shop生产调度问题的量子进化算法*

基于量子计算理论和进化理论,提出了用于多目标job-shop优化的量子进化算法（QEA-MOJSP）。QEA-MOJSP采用量子比特来表示工序对加工顺序的优先概率,利用量子叠加和相干机理,通过更新和交叉操作完成进化过程。对所有机器上工序对优先概率进行观测可得到一个调度方案,修补算子被用于不可行调度方案的修补。设计了局部搜索算子用于开采当代最优个体周围的解空间,以提高算法的收敛速度。实验结果表明,对于测试算例,QEA-MOJSP的解接近Pareto最优解集前沿,并具有很好的多样性。     

一种基于强化学习的作业车间动态调度方法

Production scheduling is critical to manufacturing system. Dispatching rules are usually applied dynamically to schedule the job in a dynamic job-shop. Existing scheduling approaches sel- dom address machine selection in the scheduling process. Composite rules, considering both machine selection and job selection, are proposed in this paper. The dynamic system is trained to enhance its learning and adaptive capability by a reinforcement learning (RL) algorithm. We define the conception of pressure to describe the system feature. Designing a reward function should be guided by the scheduling goal to accurately record the learning progress. Competitive results with the RL-based approach show that it can be used as real-time scheduling technology.     

A Reinforcement Learning-based Approach to Dynamic Job-shop Scheduling

Production scheduling is critical to manufacturing system.Dispatching rules are usually applied dynamically to schedule (?)he job in a dynamic job-shop.Existing scheduling approaches sel- dom address machine selection in the scheduling process.Composite rules,considering both machine selection and job selection,are proposed in this paper.The dynamic system is trained to enhance its learning and adaptive capability by a reinforcement learning(RL)algorithm.We define the concep- tion of pressure to describe the system feature.Designing a reward function should be guided by the scheduling goal to accurately record the learning progress.Competitive results with the RL-based approach show that it can be used as real-time scheduling technology.     

Group shops scheduling with makespan criterion subject to random release dates and processing times

This paper deals with a stochastic group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the other shop scheduling problems such as the flow shop, the job shop and the open shop scheduling problems. Both the release date of each job and the processing time of each job on each machine are random variables with known distributions. The objective is to find a job schedule which minimizes the expected makespan. First, the problem is formulated in a form of stochastic programming and then a lower bound on the expected makespan is proposed which may be used as a measure for evaluating the performance of a solution without simulating. To solve the stochastic problem efficiently, a simulation optimization approach is developed that is a hybrid of an ant colony optimization algorithm and a heuristic algorithm to generate good solutions and a discrete event simulation model to evaluate the expected makespan. The proposed approach is tested on instances where the random variables are normally, exponentially or uniformly distributed and gives promising results.     

多目标FJSP的一维编码粒子群优化求解方法

以单件小批量生产方式为主的柔性车间调度中,快速得到满足低生产成本、高生产效率,避免瓶颈发生的调度方案,是调度优化算法的设计目标。就此建立了以制造期、机床总负荷和单机最大负荷为综合目标的柔性车间调度问题（Flexible Job-shop Scheduling Problems,FJSP）优化模型;设计了一种以概率值为分量的一维粒子群优化算法,通过概率区间划分将连续粒子分量离散化,结合完工时间最早启发式规则,实现工序的排序与加工机床的选取。通过不同规模算例的比较,分析结果表明该方法在求解较大规模问题时具有一定的优势。     

A heuristic N-jobs/M-machines scheduling algorithm

This paper presents a heuristic algorithm to minimize the makespan of the N-job/M-machine job-shop scheduling problem.

The algorithm is based on the assumption that the (different) technological ordering of machines for each job is deterministic and that the problem is static. Hauristic priority rules are used to determine the job with the highest priority at each (scheduling) stage.

The illustrative example demonstrates the systematic iteration to accomplish the scheduling.     

Flexible job-shop scheduling with parallel variable neighborhood search algorithm

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. FJSP is NP-hard and mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines. This paper proposes a parallel variable neighborhood search (PVNS) algorithm that solves the FJSP to minimize makespan time. Parallelization in this algorithm is based on the application of multiple independent searches increasing the exploration in the search space. The proposed PVNS uses various neighborhood structures which carry the responsibility of making changes in assignment and sequencing of operations for generating neighboring solutions. The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the FJSP.     

采用优先规则的粒子群算法求解RCPSP

优先规则是解决大规模资源受限的项目调度问题（Resource-Constrained Project Scheduling Problem,RCPSP）强有力的方法,但是单一的优先规则的往往仅在某些特定的问题上表现出良好的性能。以粒子群算法为基础,提出了基于优先规则编码的粒子群算法（Priority Rule based Particle Swarm Optimization,PRPSO）,求解资源受限的项目调度问题。该方法能够通过粒子群算法搜索优先规则和调度生成方案的组合。分别对PRPSO采用串行调度方案、并行调度方案和混合调度方案时,不同任务数和资源强度的问题实例进行了分析。通过对PSPLIB进行测试,结果表明该方法与其它基于优先规则的启发式方法相比有较低的偏差率,因而有较好的性能。     

工件工序可并行的作业车间调度模型与求解

针对传统作业车间调度模型没有考虑工件工序存在并行性的不足,提出一种以最小化完工时间为目标的工件工序可并行作业车间调度模型,且在模型中考虑了工序加工设备柔性;设计了基于遗传算法的调度算法,其中染色体编码采用分段编码方式,并提出一种适用于工件工序存在并行性的染色体解码方法.实验结果表明,文中算法能够有效地解决工件工序可并行的作业车间调度问题.     

Greedy randomized adaptive search for dynamic flexible job-shop scheduling

Dynamic flexible job shop scheduling problem is studied under the events such as new order arrivals, changes in due dates, machine breakdowns, order cancellations, and appearance of urgent orders. This paper presents a constructive algorithm which can solve FJSP and DFJSP with machine capacity constraints and sequence-dependent setup times, and employs greedy randomized adaptive search procedure (GRASP). Besides, Order Review Release (ORR) mechanism and order acceptance/rejection decisions are also incorporated into the proposed method in order to adjust capacity execution considering customer due date requirements. The lexicographic method is utilized to assess the objectives: schedule instability, makespan, mean tardiness and mean flow time. A group of experiments is also carried out in order to verify the suitability of the GRASP in solving the flexible job shop scheduling problem. Benchmark problems are formed for different problem scales with dynamic events. The event-driven rescheduling strategy is also compared with periodical rescheduling strategy. Results of the extensive computational experiment presents that proposed approach is very effective and can provide reasonable schedules under event-driven and periodic scheduling scenarios.     

Reactive scheduling in a job shop where jobs arrive over time

The paper considers the dynamic job shop scheduling problem (DJSSP) with job release dates which arises widely in practical production systems. The principle characteristic of DJSSP considered in the paper is that the jobs arrive continuously in time and the attributes of the jobs, such as the release dates, routings and processing times are not known in advance, whereas in the classical job shop scheduling problem (CJSSP), it is assumed that all jobs to be processed are available at the beginning of the scheduling process. Reactive scheduling approach is one of the effective approaches for DJSSP. In the paper, a heuristic is proposed to implement the reactive scheduling of the jobs in the dynamic production environment. The proposed heuristic decomposes the original scheduling problem into a number of sub problems. Each sub problem, in fact, is a dynamic single machine scheduling problem with job release dates. The scheduling technique applied in theproposed heuristic is priority scheduling, which determines the next state of the system based on priority values of certain system elements. The system elements are prioritized with the help of scheduling rules (SRs). An approach based on gene expression programming (GEP) is also proposed in the paper to construct efficient SRs for DJSSP. The rules constructed by GEP are evaluated in the comparison of the rules constructed by GP and several prominent human made rules selected from literatures on extensive problem sets with respect to various measures of performance.     

柔性作业车间调度分析及其启发式算法

针对多目标柔性作业车间调度问题,基于甘特图和搭积木经验进行了分析,提出了一种组合优先规则和基于此优先规则的启发式算法。组合优先规则面向完工时间、关键机床负荷和总负荷三个指标,改变规则中各数据项的比例可调整三个指标所占的比例。算法采用随机方式调整三个指标的比例,并微调最优解对应的比例,能随机产生多个高质量调度解。对比测试表明,算法求解质量更高,运行速度快,稳定,可直接用于在其他调度算法中产生初始解,或者用于动态调度。     

Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach

In scheduling problems, taking the sequence-dependent setup times into account is one of the important issues that have recently been considered by researchers in the production scheduling field. In this paper, we consider flexible job-shop scheduling problem (FJSP) with sequence-dependent setup times to minimize makespan and mean tardiness. The FJSP consists of two sub-problems from which the first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on all machines. To solve this problem, a variable neighborhood search (VNS) algorithm based on integrated approach is proposed. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed the search process. To search the solution space, the internal loop used two main search engines, i.e. shake and local search procedures. In addition, neighborhood structures related to the sequencing problem and the assignment problem were employed to generate neighboring solutions. To evaluate the performance of the proposed algorithm, 20 test problems in different sizes are randomly generated. Consequently, computational results and comparisons validate the quality of the proposed approach.     

An effective heuristic for flexible job-shop scheduling problem with maintenance activities

Most production scheduling problems, including the standard flexible job-shop scheduling problem (FJSP), assume that machines are continuously available. However, in most realistic situations, machines may become unavailable during certain periods due to preventive maintenance (PM). In this paper, a flexible job-shop scheduling problem with machine availability constraints is considered. Each machine is subject to preventive maintenance during the planning period and the starting times of maintenance activities are either flexible in a time window or fixed beforehand. Moreover, two cases of maintenance resource constraint are considered: sufficient maintenance resource available or only one maintenance resource available. To deal with this variant FJSP problem with maintenance activities, a filtered beam search (FBS) based heuristic algorithm is proposed. With a modified branching scheme, the machine availability constraint and maintenance resource constraint can be easily incorporated into the proposed algorithm. Simulation experiments are conducted on some representative problems. The results demonstrate that the proposed filtered beam search based heuristic algorithm is a viable and effective approach for the FJSP with maintenance activities.     

考虑非确定加工时间的柔性作业车间调度问题研究

加工时间不确定的柔性作业车间调度问题已逐渐成为生产调度研究的热点。采用区间表示加工时间范围,利用时间Petri网建立区间柔性作业车间调度问题形式化模型,并运用网模型的状态类图进行可达性分析,计算出所有可行变迁触发序列。通过对触发序列的时序分析,提出一种有效的逆向分步法来构造触发序列的时间约束不等式,进而求解线性规划问题来获得最小完工时间下界(上界)的优化调度策略。最后利用实例分析验证了模型及所提方法的正确性和可行性,为实际的区间柔性作业车间调度问题提供有效方案。     

基于关键链的资源受限项目调度新方法

针对资源受限项目调度问题（RCPSPs）的实际需求建立了多目标优化调度模型，综合运用现有研究成果，设计了基于关键链的项目调度方法。该方法首先采用基于优先规则的启发式算法生成工期最小的近优项目计划，再在该计划中嵌入输入缓冲和项目缓冲，保证项目计划在非确定环境下的稳定执行。论文引用RCPSPs的标准问题库PSPLIB中大量案例对算法进行了的仿真试验，结果表明本文方法较传统项目调度方法有很大改进，论文最后对仿真结果进行了深入讨论，并指出了未来的研究方向。     

A two-machine flowshop scheduling problem with a separated maintenance constraint

This paper considers a two-machine flowshop scheduling problem with a separated maintenance constraint. This means that the machine may not always be available during the scheduling period. It needs a constant time to maintain the machine after completing a fixed number of jobs at most. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem has some practical applications, for example, in electroplating process, the electrolytic cell needs to be cleaned and made up a deficiency of medicine. In this paper, we propose a heuristic algorithm to solve this problem. Some polynomially solvable cases and computational experiments are also provided.     

基于蚁群粒子群算法求解多目标柔性调度问题

通过分析多目标柔性作业车间调度问题中各目标的相互关系，提出一种主、从递阶结构的蚁群粒子群求解算法。算法中，主级为蚁群算法，在选择工件加工路径过程中实现设备总负荷和关键设备负荷最小化的目标；从级为粒子群算法，在主级工艺路径约束下的设备排产中实现工件流通时间最小化的目标。然后，以设备负荷和工序加工时间为启发式信息设计蚂蚁在工序可用设备间转移概率；基于粒子向量优先权值的大小关系设计解码方法实现设备上的工序排产。最后，通过仿真和比较实验，验证了该算法的有效性。