考虑生产过程时间的柔性作业车间调度优化

通过研究生产过程时间,重新细分和定义等待时间,建立包括运输时间、调整时间、故障时间、等待时间、加工时间在内的柔性作业车间生产过程的时间模型,研究了柔性作业车间调度优化问题并设计了混合遗传算法的求解算法。最后,采用经典柔性作业车间调度用例,验证和对比了柔性作业车间调度的结果。结果表明,基于生产过程时间模型研究柔性作业车间调度问题,其优化性能有较好的改进,具有更好的实际应用价值。     

具有工序顺序柔性的车间调度问题研究综述

某些加工车间在生产过程中具有多种柔性,工序顺序柔性就是其中重要的一种。通过对具有工序顺序柔性的车间调度问题的优化求解,能够极大地提高生产效率,节约生产成本。本文对具有工序顺序柔性的车间调度问题的研究现状进行整理分析,主要包括混合车间调度问题(mixed shop scheduling problem, MSP)、分组车间调度问题(group shop scheduling problem, GSP)和部分车间调度问题(partial shop scheduling problem, PSP)。最后,指出了具有工序顺序柔性的车间调度问题的发展前景及发展方向。     

基于改进遗传算法的偏柔性作业车间调度

偏柔性作业车间调度是生产管理中的重要问题。由于模型和计算的复杂性,传统优化方法往往难以得到最优解。采用改进遗传算法求解偏柔性作业车间的调度问题,设计相应的编码方法,利用所生成的染色体以及通过遗传操作得到的染色体生成可行的调度方案。基于工序串和机器串的编码方法,采用精英解保留策略、轮盘赌选择策略和基于划分集的交叉策略,提出基于均匀分布试验的变异法则,引入贪婪式解码方法对偏柔性作业车间调度进行求解。实例仿真表明,该算法在求解偏柔性作业车间调度方面具有良好的效率和优越性。     

基于深度强化学习的柔性作业车间节能调度研究

针对当前柔性作业车间节能调度研究无法充分利用历史生产数据,且对复杂、动态、多变的车间生产环境适应性不足的问题,引入深度强化学习思想,利用具有代表性的深度Q网络（deep Q-network, DQN）求解柔性作业车间节能调度问题。将柔性作业车间节能调度问题转化为强化学习对应的马尔科夫决策过程。进而,提炼表征车间生产状态特征的状态值作为神经网络输入,通过神经网络拟合状态值函数,输出复合调度动作规则实现对工件以及加工机器的选择,并利用动作规则与奖励函数协同优化能耗。在3个不同规模的案例上与非支配排序遗传算法、超启发式遗传算法、改进狼群算法等典型智能优化方法进行求解效果对比。结果表明,DQN算法有较强的搜索能力,且最优解分布情况与提出的柔性作业车间节能调度模型聚焦能耗目标相一致,从而验证了所用DQN方法的有效性。     

应用改进蚁群算法求解柔性作业车间调度问题

将蚁群算法信息素更新规则进行改进,规定只有产生至今最优解的蚂蚁才能释放信息素,且只更新全局信息素,减少了传统蚁群算法的时间复杂度,提高了问题的求解效率。分析了柔性作业车间调度的特点,选取三个性能指标作为求解目标,设定其求解优先级,并建立相应的调度模型。将改进蚁群算法应用于柔性作业车间调度算例的求解,与其它算法比较,平均解有很大提高,表明了该算法求解柔性作业车间调度问题的有效性。     

基于MAS车间调度系统模型的设计

本文在对车间调度存在问题分析基础上,设计了基于MAS技术的车间调度系统模型,使各不同代理之间通过KQML语言进行通信,并按照合同网协议进行彼此协商,从而高效的完成了柔性制造业企业中的车间调度任务。     

改进遗传算法解决柔性作业车间调度问题

柔性作业车间调度问题是经典作业车间调度问题的扩展,它允许工序在多台机器中的任意一台上加工.针对柔性作业车间调度问题的特点,提出一种扩展的基于工序的编码及其主动调度的解码机制,并设计一种初始解产生机制和两种有效的交叉和变异操作.为了克服传统遗传算法早熟和收敛慢的缺点,设计了精英解保留策略和子代产生模式结合的改进遗传算法应用于该调度问题.最后运用提出的算法求解基准测试问题验证算法的有效性.     

基于三方博弈的改进遗传算法求解多目标柔性作业车间调度

针对柔性作业车间的特点,以最小化完工时间、总机器负荷最小和临界机器负荷最小为目标,提出了基于三方博弈的改进遗传算法求解多目标柔性作业车间调度模型。通过三方博弈,使三个优化目标之间的博弈策略实现最优组合,从而获得子博弈完美纳什均衡,即为问题的优化组合解。为优化种群质量,将改进遗传算法应用于多目标柔性作业车间调度问题的求解过程,采用帕累托分类思想,对种群进行选择和精英保留,以优化种群结构;通过设计交叉、变异和局部搜索机制进一步寻找目标函数的最优解。为证明算法的有效性,运用基准算例对算法的求解性能进行了验证。其结果表明,所提算法在求解结果上有明显的改善,求解效率更高。     

改进遗传算法求解多时间约束的柔性作业车间调度问题

将加工时间、调整时间和移动时间分别作为独立时间因素考虑到柔性作业车间调度模型中,建立以最大完工时间最小、总调整时间最小、总移动时间最小为目标的考虑多时间约束的柔性作业车间调度模型,并提出改进的遗传算法求解该模型。通过测试标准数据集,并对比其他文献算法,验证了改进的遗传算法的可行性和有效性。     

分布式FMS的非递阶调度控制

针对ＦＭＳ车间调度控制问题提出一种分布式协同调度控制的思想，从而简化了控制结构，降低了复杂性，提出了系统的容错能力及其柔性。在该模型中存在多个生产实体，不同的实体前置有一个智能协调控制器（ＩＳＣ），通过广播协商机制达到自组织和自决策。所有的智能协调控制器并发运行，以完成整修车间的在线调度控制，该系统避免了传统的集中调度控制的许多缺点，为实现柔性车间调度控制探索了一条新的途径。     

A memetic algorithm for multi-objective flexible job-shop problem with worker flexibility

In existing scheduling models, the flexible job-shop scheduling problem mainly considers machine flexibility. However, human factor is also an important element existing in real production that is often neglected theoretically. In this paper, we originally probe into a multi-objective flexible job-shop scheduling problem with worker flexibility (MO-FJSPW). A non-linear integer programming model is presented for the problem. Correspondingly, a memetic algorithm (MA) is designed to solve the proposed MO-FJSPW whose objective is to minimise the maximum completion time, the maximum workload of machines and the total workload of all machines. A well-designed chromosome encoding/decoding method is proposed and the adaptive genetic operators are selected by experimental studies. An elimination process is executed to eliminate the repeated individuals in population. Moreover, a local search is incorporated into the non-dominated sorting genetic algorithm II. In experimental phase, the crossover operator and elimination operator in MA are examined firstly. Afterwards, some extensive comparisons are carried out between MA and some other multi-objective algorithms. The simulation results show that the MA performs better for the proposed MO-FJSPW than other algorithms.     

A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem

Scheduling for the flexible job-shop is a very important issue in both fields of combinatorial optimization and production operations. However, due to combination of the routing and sequencing problems, flexible job-shop scheduling problem (FJSP) presents additional difficulty than the classical job-shop scheduling problem and requires more effective algorithms. This paper developed a filtered-beam-search-based heuristic algorithm (named as HFBS) to find sub-optimal schedules within a reasonable computational time for the FJSP with multiple objectives of minimising makespan, the total workload of machines and the workload of the most loaded machine. The proposed algorithm incorporates dispatching rules based heuristics and explores intelligently the search space to avoid useless paths, which makes it possible to improve the search speed. Through computational experiments, the performance of the presented algorithm is evaluated and compared with those of existing literature and those of commonly used dispatching rules, and the results demonstrate that the proposed algorithm is an effective and practical approach for the FJSP.     

Solving Job-Shop Scheduling Problems by Genetic Algorithms Based on Building Block Hypothesis

In this paper, we propose a new genetic algorithm for job-shop scheduling problems （JSP）. The proposed method uses the operation-based representation, based on schema theorem and building block hypothesis, a new crossover is proposed ： By selecting short, low order highly fit schemas to genetic operator, the crossover can exchange meaningful ordering information of parents effectively and can search the global optimization. Simulation results on MT benchmark problem coded by C ＋ ＋ show that our genetic operators are very powerful and suitable to job-shop scheduling problems and our method outperforms the previous GA-based approaches.     

Mixed Self-adapting GA Optimal Scheduling Algorithm for a Multiple Resource Job-shop

With an aim at the job-shop scheduling problem of multiple resource constraints, this paper presents mixed self-adapting Genetic Algorithm （ GA ） , and establishes a job-shop optimal scheduling model of multiple resource constraints based on the effect of priority scheduling rules in the heuristic algorithm upon the scheduling target. New coding regulations or rules are designed. The sinusoidal function is adopted as the self-adapting factor, thus making cross probability and variable probability automatically change with group adaptability in such a way as to overcome the shortcoming in the heuristic algorithm and common GA, so that the operation efficiency is improved. The results from real example simulation and comparison with other algorithms indicate that the mixed self-adapting GA algorithm can well solve the job-shop optimal scheduling problem under the constraints of various kinds of production resources such as machine-tools and cutting tools.     

A variable neighbourhood search algorithm for the flexible job-shop scheduling problem

The flexible job-shop scheduling problem (FJSP) is a generalisation of the classical job-shop scheduling problem which allows an operation of each job to be executed by any machine out of a set of available machines. FJSP consists of two sub-problems which are assigning each operation to a machine out of a set of capable machines (routing sub-problem) and sequencing the assigned operations on the machines (sequencing sub-problem). This paper proposes a variable neighbourhood search (VNS) algorithm that solves the FJSP to minimise makespan. In the process of the presented algorithm, various neighbourhood structures related to assignment and sequencing problems are used for generating neighbouring solutions. To compare our algorithm with previous ones, an extensive computational study on 181 benchmark problems has been conducted. The results obtained from the presented algorithm are quite comparable to those obtained by the best-known algorithms for FJSP.     

混合花朵授粉算法在作业车间调度中的应用

对最大完工时间最短的作业车间调度问题进行了研究,总结了当前求解作业车间调度问题的研究现状,提出一种花朵授粉算法与遗传算法的混合算法。混合算法以花朵授粉算法为基础,重新定义其全局搜索和局部搜索迭代公式,在同化操作过程中融入遗传算法的选择、优先交叉和变异操作,进一步增强算法的勘探能力。通过26个经典的基准算例仿真实验,并与近5年的其他算法比较,结果表明所提算法在求解作业车间调度问题具有一定优势。     

A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times

In real scheduling problems, unexpected changes may occur frequently such as changes in task features. These changes cause deviation from primary scheduling. In this article, a heuristic model, inspired from Artificial Bee Colony algorithm, is proposed for a dynamic flexible job-shop scheduling (DFJSP) problem. This problem consists of n jobs that should be processed by m machines and the processing time of jobs deviates from estimated times. The objective is near-optimal scheduling after any change in tasks in order to minimise the maximal completion time (Makespan). In the proposed model, first, scheduling is done according to the estimated processing times and then re-scheduling is performed after determining the exact ones considering machine set-up. In order to evaluate the performance of the proposed model, some numerical experiments are designed in small, medium and large sizes in different levels of changes in processing times and statistical results illustrate the efficiency of the proposed algorithm.     

Research on job-shop scheduling problem based on genetic algorithm

With job-shop scheduling (JSS) it is usually difficult to achieve the optimal solution with classical methods due to a high computational complexity (NP-hard). According to the nature of JSS, an improved definition of the JSS problem is presented and a JSS model based on a novel algorithm is established through the analysis of working procedure, working data, precedence constraints, processing performance index, JSS algorithm and so on. A decode select string (DSS) decoding genetic algorithm based on operation coding modes, which includes assembly problems, is proposed. The designed DSS decoding genetic algorithm (GA) can avoid the appearance of infeasible solutions through comparing current genes with DSS in the decoding procedure to obtain working procedure which can be decoded. Finally, the effectiveness and superiority of the proposed method is clarified compared to the classical JSS methods through the simulation experiments and the benchmark problem.     

Flexible job-shop scheduling problem under resource constraints

A flexible job-shop-scheduling problem is an extension of classical job-shop problems that permit an operation of each job to be processed by more than one machine. The research methodology is to assign operations to machines (assignment) and determine the processing order of jobs on machines (sequencing) such that the system objectives can be optimized. This problem can explore very well the common nature of many real manufacturing environments under resource constraints. A genetic algorithm-based approach is developed to solve the problem. Using the proposed approach, a resource-constrained operations–machines assignment problem and flexible job-shop scheduling problem can be solved iteratively. In this connection, the flexibility embedded in the flexible shop floor, which is important to today's manufacturers, can be quantified under different levels of resource availability.     

An effective estimation of distribution algorithm for the flexible job-shop scheduling problem with fuzzy processing time

Considering the fuzzy nature of the data in real-world scheduling, an effective estimation of distribution algorithm (EDA) is proposed to solve the flexible job-shop scheduling problem with fuzzy processing time. A probability model is presented to describe the probability distribution of the solution space. A mechanism is provided to update the probability model with the elite individuals. By sampling the probability model, new individuals can be generated among the search region with promising solutions. Moreover, a left-shift scheme is employed for improving schedule solution when idle time exists on the machine. In addition, some fuzzy number operations are used to calculate scheduling objective value. The influence of parameter setting is investigated based on the Taguchi method of design of experiment, and a suitable parameter setting is suggested. Numerical testing results and comparisons with some existing algorithms are provided, which demonstrate the effectiveness of the proposed EDA.