考虑工序相关性的动态Job shop调度问题启发式算法

提出一类考虑工序相关性的、工件批量到达的动态Job shop 调度问题,在对工序相关性进行了定义和数学描述的基础上,进一步建立了动态Job shop 调度问题的优化模型。设计了一种组合式调度规则RAN(FCFS,ODD),并提出了基于规则的启发式算法以及该类动态Job shop 调度问题的算例生成方法。为验证算法和比较评估调度规则的性能,对算例采用文献提出的7种调度规则和RAN(FCFS,ODD)进行了仿真调度,对调度结果的分析表明了算法的有效性和RAN(FCFS,ODD)调度规则求解所提出的动态Job Shop 调度问题的优越性能。     

双资源约束的鲁棒Job Shop调度问题研究

针对机器-工人双资源约束下加工时间具有随机性的Job shop调度问题(Job shop scheduling problems,JSSP),考虑工人熟练程度差异和工人数量不足的约束,采用鲁棒调度的方法建立机器-工人双资源约束的鲁棒Job shop调度模型(Dual-resource constrained robust JSSP,DR-RJSSP).鉴于DR-RJSSP同时考虑工人合理指派和双目标优化,提出机器-工人两阶段指派方法,在主动降低加工时间随机扰动的同时最小化工人约束对调度性能的影响.其次,提出多目标混合分布估计算法求解DR-RJSSP,以得到兼顾调度性能和鲁棒性的Pareto解集.最后,采用8组仿真算例将所提出的兼顾工人熟练程度和负载均衡的指派策略与基于熟练程度的指派策略和随机指派策略进行对比,验证了所提指派策略的Pareto优化性能.此外,通过对制造企业调度案例的仿真分析,验证了基于两阶段指派策略的MO-HEDA求解DR-RJSSP的有效性.     

解决JOB SHOP问题的粒子群优化算法

设计了2种解决Job shop问题的粒子群算法,即实数编码的粒子群调度算法和工序编码的粒子群调度算法。工序编码的粒子群调度算法更符合Job shop问题的特点,优化性能相对高。但粒子群调度算法容易陷入局部最优。为了提高优化性能,将粒子群算法和模拟退火算法结合,得到了粒子群-模拟退火混合调度算法。仿真结果表明了算法的有效性。     

基于深度强化学习的工序交互式智能体Job shop调度方法

针对作业车间调度问题(Job shop scheduling problem, JSSP)因NP-难属性难以快速获得优质解,以及生产场景随机扰动所导致的频繁重调度等求解难题,基于深度强化学习提出一种新颖的交互式工序智能体(Interactive operation agent, IOA)调度模型框架。在分析工序间工艺路线和加工设备约束关系的基础上,将Job shop的加工工序构建为工序智能体,设计工序智能体间的交互机制,智能体依据彼此关系进行特征交互并更新自身的特征向量,并基于工序特征和最早加工时间设计拟合动作值函数的深度神经网络,调度模型根据系统状态和工序智能体特征即可生成调度策略。采用Double DQN算法训练IOA调度模型,引入经验回放机制消除序列训练样本间的相关性,训练好的模型可以快速生成高质量的调度方案,并在机器发生故障时能够有效执行重调度策略。试验结果表明所提出的IOA调度方法优于贪婪算法和启发式调度规则,且具有良好鲁棒性和泛化能力。     

工件到达时间未知的动态车间滚动重调度

研究工件动态到达且到达时间未知的车间重调度问题,目标是最小化所有工件的拖期和.动态事件频繁的调度环境,对调度算法的计算效率要求很高.在滚动时域分解方法框架下,提出关键工序集的概念,采用混合遗传算法确定关键工序集合及其对应的最优部分调度.在解码过程中,采用混合调度生成器将染色体中的基因转化为部分可行调度,对没有参与遗传进化的工序采用改进的修正交货期(Modified due date,MDD)规则确定其在机器上的加工顺序,以完全调度的目标值评价染色体的适应度.对大量算例的仿真表明基于关键工序集的重调度算法对动态事件的响应速度,大大优于基于完全工序集的重调度算法,并且具有良好的全局性能,兼顾了实际动态Job shop系统对调度性能和计算效率的要求.     

一种求解加工时间离散可控作业车间调度问题的混合算法

加工时间离散可控作业车间调度问题(Job-shop scheduling problem with discretely controllable processing times,JSP-DCPT)是经典作业车间调度问题(Job-shop scheduling problem,JSP)的一类扩展问题。为避免通过多项式时间近似方法求解JSP-DCPT的近似问题,提出一种混合算法直接求解JSP-DCPT。该算法基于分解方法,嵌套一种禁忌搜索模拟退火混合算法TSSA和一种快速精英保留非支配排序遗传算法NSGA-II,以分别高效求解JSP-DCPT分解所得的JSP子问题和离散时间—成本权衡子问题。基于JSP标准算例FT06,FT10和FT20构造3个不同问题规模的测试算例,试验仿真结果表明,混合算法能够得到收敛的帕累托边界。     

Job Shop基于无延迟调度路径重连与回溯禁忌搜索算法研究

针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种路径重连和禁忌搜索混合算法.结合JSP领域知识设计路径重连,分别将正向无延迟调度解和反向无延迟调度解作为导向解.在正向无延迟和反向无延迟调度甘特图中,每一道工序的左边与右边分别无可用空闲时间.提出基于当前解工序头长度的正向无延迟调度转化算法,以及反转工件工艺路线,基于当前解工序尾长度的反向无延迟调度转化算法.设计新的基于精英解的回溯禁忌搜索算法,能够充分利用迭代过程中的历史解信息.不但提取更新的当前最优解加入到精英解集合,而且当最优解连续不更新代数达到设定值时,提取区间代数内较好的当前解加入到精英解集合.实现精英解池的不断补充和动态更新,使得算法可以持续进行回溯搜索.采用移动范围更广的邻域结构进行搜索,将路径重连与禁忌搜索算法混合,对JSP问题基准算例进行测试,验证了所提算法的有效性.     

基于新型邻域结构的混合算法求解作业车间调度

针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种融合新型邻域结构的混合求解方法。混合算法由具有全局搜索能力的遗传算法和基于邻域结构的邻域搜索算法构成。在邻域结构的设计中,研究了基于甘特图的工序头尾长度计算方法,以及关键工序查找方法。通过分析已有各种邻域结构及相关理论性质,指出邻域结构的根本在于引导关键工序对机器空闲时间进行利用,并将利用方式分为两种情况:直接利用和间接利用。综合两种利用方式,科学指导关键工序的移动,根据关键工序的类型定义相应的移动操作,使其移动范围突破了工序块的内部、紧前、紧后位置限制,扩大了有效移动范围。结合43个基准算例进行测试分析,验证了所提算法具有良好的求解性能。此外,所设计的邻域结构可以进一步融合其他智能算法求解JSP问题。     

带模糊排序的移动瓶颈法求解不确定调度问题

综合应用模糊排序法和移动瓶颈法（Shifting Bottleneck Procedures．SBP）来求解加工时间不确定的Job—shop调度问题。首先对移动瓶颈法作简要介绍,并给出将模糊数转换为确定数的相关方程式．然后通过一个实际的算例演示该算法的详细求解过程。结果表明,该算法可用来有效求解一类带模糊加工时间的Job—shop调度问题。     

改进混合Jaya优化算法求解柔性作业车间调度问题

针对柔性作业车间调度问题(Flexible Job shop Scheduling Problem,FJSP),以最小化最大完工时间为优化目标,在研究现有Jaya优化算法的基础上,结合邻域搜索算法,提出一种改进混合Jaya优化算法.首先,针对MSOS编码方式设计种群初始化方法;其次,提出一种基于Jaya优化算法思想的离散化更新算子,使算法适用于FJSP;然后,设计了2种新型邻域结构,有效增强了算法的局部寻优能力;最后,通过3组著名的FJSP基准算例进行测试,并与相同目标的其他算法进行对比分析.结果 表明,改进混合Jaya优化算法能有效求解FJSP,且比相同目标的其他算法有更强的求解能力.     

Application of chance-constrained programming for stochastic group shop scheduling problem

In this paper, we study a group shop scheduling (GSS) problem subject to uncertain release dates and processing times. The GSS problem is a general formulation including the other shop scheduling problems such as the flow shop, the job shop, and the open shop scheduling problems. The objective is to find a job schedule which minimizes the total weighted completion time. We solve this problem based on the chance-constrained programming. First, the problem is formulated in a form of stochastic programming and then prepared in a form of deterministic mixed binary integer linear programming such that it can be solved by a linear programming solver. To solve the problem efficiently, we develop an efficient hybrid method. Exploiting a heuristic algorithm in order to satisfy the constraints, an ant colony optimization algorithm is applied to construct high-quality solutions to the problem. The proposed approach is tested on instances where the random variables are normally, uniformly, or exponentially distributed.     

Group shop scheduling with uncertain data and a general cost objective

In this paper, a stochastic group shop scheduling problem with a due date-related objective is studied. The group shop scheduling problem provides a general formulation including two other shop scheduling problems, the job shop and the open shop. Both job release dates and processing times are assumed to be random variables with known distributions. Moreover, earliness and tardiness of jobs are penalized at different rates. The objective is to minimize the expected maximum completion cost among all jobs. A lower bound on the objective function is proposed, and then, a hybrid approach following a simulation optimization procedure is developed to deal with the problem. An ant colony optimization algorithm is employed to construct good feasible solutions, while a discrete-event simulation model is used to estimate the performance of each constructed solution that, taking into account its lower bound, may improve the best solution found so far. The proposed approach is then evaluated through computational experiments.     

面向随机加工时间的车间作业调度

提出了面向随机加工时间的车间作业调度方法,认为在整个遗传进化过程中出现频率越高的个体对环境的适应能力越强,该个体对应的调度方案为较优方案,构造了用于解决加工时间为服从正态分布的随机变量的车间作业调度问题的扩展遗传算法.在算法中设计了考虑设备能力空间的解码算法以产生活动调度方案;在交叉/变异过程中通过设计的基因调整算法确保新个体的合法性,以满足工序约束;采用基于适应值的轮盘赌的选择策略控制遗传进化的方向,使算法快速收敛到最优解.仿真实验验证了该算法在企业实际随机车间作业调度中的有效性.     

基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法*

将逆优化理论与方法引入车间调度领域,探讨近年来车间调度领域出现的一种新方法“逆调度”。研究多目标流水车间逆调度问题,建立考虑调度效率和调度稳定性的数学模型,综合考虑了加工参数改变量、系统改变量以及完工时间和等目标。提出一种基于混合的多目标遗传算法(Hybrid multi-objective genetic algorithm, HMGA)的求解方法,将多种策略进行混合以提高算法性能,主要包括快速非支配排序遗传算法(Non-dominated sorting genetic algorithm II, NSGAII)中的快速非支配排序方法、两种多样性保持策略、混合的精英保留策略,以及改进的局部搜索策略等。通过实例测试与方差分析(Analysis of variance, ANOVA),验证了该算法的有效性。     

可调加工时间炼钢-连铸的灰狼优化调度算法

炼钢-连铸(SCC)是钢铁生产中的瓶颈,SCC生产过程中最后一个阶段的加工时间可调。可调加工时间SCC调度问题是NP难组合优化问题,高质量的SCC调度算法可以较大地提高生产效率。基于问题特征,研制了求解该问题的高效灰狼优化(GWO)算法。首先设计了新的解码方法对解进行解码。同时提出了种群初始化方法,以得到具有一定质量和多样性的初始种群。其次,研制了一种基于多操作的搜索算子,该算子包含3种不同操作,在一定程度上实现了GWO算法的集中性和多样性的平衡。此外,设计了重启操作,以提高GWO算法的多样性。对比实验说明了基于多操作的搜索算子的有效性。此外,与4种有效调度方法的对比说明了GWO算法的高性能和优越性。     

Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns

Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. Furthermore, most scheduling problems which have been discussed in the literature are under the assumption that machines are continuously available. Nevertheless, in most real life industries, a machine can be unavailable for many reasons, such as unanticipated breakdowns, i.e., stochastic unavailability, or due to a scheduled preventive maintenance where the periods of unavailability are known in advance, i.e., deterministic unavailability. This paper deals with the hybrid flow shop scheduling problems in which there are sequence-dependent setup times, commonly known as the SDST, and machines which suffer stochastic breakdown to optimize objectives based on expected makespan. This type of production system is found in industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacture. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. The genetic algorithm can be used to tackle complex problems and produce a reasonable manufacturing schedule within an acceptable time. This paper describes how we can incorporate simulation into genetic algorithm approach to the scheduling of a SDST hybrid flow shop with machines that suffer stochastic breakdown. An overview of the hybrid flow shops and scheduling under stochastic unavailability of machines are presented. Subsequently, the details of incorporated simulation into genetic algorithm approach are described and implemented. Consequently, the results obtained are analyzed with Taguchi experimental design.     

Stochastic simulation of electron-hole recombination in two-dimensional and three-dimensional inhomogeneous semiconductors. Part I. Stochastic model and algorithms

This paper describes the stochastic models of electron-hole recombination in inhomogeneous semiconductors in two-dimensional and three-dimensional cases, which were developed on the basis of discrete (cellular automation) and continuous (Monte Carlo method) approaches. The mathematical model of electron-hole recombination, constructed on the basis of a system of spatially inhomogeneous nonlinear integro-differential Smoluchowski equations, is illustrated. The continuous algorithm of the Monte Carlo method and the discrete cellular automation algorithm used for the simulation of particle recombination in semiconductors are shown.     

基于MCMC方法的随机加工时间研究

在分析随机作业调度问题特点的基础上,建立了随机加工时间统计模型及参数估计模型,在参数未知及参数已知的条件下,提出了基于马尔可夫链蒙特卡罗方法的随机加工时间统计技术,并通过吉布斯抽样实现了加工时间的参数估计。通过计算机仿真实验,验证了该方法的可行性及有效性,为随机作业调度提供更符合实际生产的数据支撑。     

A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times

In this paper, the unrelated parallel machine scheduling problem with sequence-dependent setup times and limited human resources is addressed with reference to the makespan minimisation objective. Workers needed for setup operations are supposed to be a critical resource as their number is assumed to be lower than the number of workstations. In addition, each worker is characterised by a specific skill level, which affects setup times. Firstly, a mathematical model able to optimally solve small instances of the problem in hand is illustrated. Then, to deal with large-sized test cases, three different optimisation procedures equipped by different encoding methods are proposed: a permutation encoding-based genetic algorithm (GA), a multi-encoding GA and a hybrid GA that properly moves from a permutation encoding to a multi-encoding once a given threshold on the number of generations is achieved. In particular, three different hybrid GAs featured by different encoding switch thresholds were implemented. An extensive benchmark including both small- and large-sized instances was generated with the aim of both calibrating the genetic parameters and comparing the alternative GAs through distinct ANOVA analyses. Numerical results confirm the effectiveness of the hybrid genetic approach whose encoding switch threshold is fixed to 25 % of the overall generations. Finally, a further analysis concerning the impact of multi-skilled workforce on the performance of both production system and optimisation strategy is presented.     

Bi-objective hybrid flow shop scheduling with sequence-dependent setup times and limited buffers

The bi-objective hybrid flow shop problem with sequence-dependent setup times and limited buffers is mentioned in this paper. In this environment, there are limited buffer spaces between any two successive stages; thus, maybe there is not enough room for queues of jobs that are waiting in the system for their next operations. This problem is shown to be NP-hard in the strong sense. Up to now, some heuristic and metaheuristic approaches are proposed to minimize makespan or total tardiness of jobs. This paper presents several methods for optimization which consider two objectives simultaneously. The resolution of several specific instances from the open literature with the adaptations of non-dominated sorting genetic algorithm and sub-population genetic algorithm suggest that the proposed algorithms are effective and useful methods for solving this problem.