考虑工件移动时间的柔性作业车间调度问题研究

分析生产车间的实际生产状况,建立了考虑工件移动时间的柔性作业车间调度问题模型,该模型考虑了以往柔性作业车间调度问题模型所没有考虑的工件在加工机器间的移动时间,使柔性作业车间调度问题更贴近实际生产,让调度理论更具现实性。通过对已有的改进遗传算法的遗传操作进行重构,设计出有效求解考虑工件移动时间的柔性作业车间调度问题的改进遗传算法。最后对实际案例进行求解,得到调度甘特图和析取图,通过对甘特图和析取图的分析验证了所建考虑工件移动时间的柔性作业车间调度问题模型的可行性和有效性。     

遗传算法解柔性作业车间调度问题应用综述

柔性作业车间调度问题是典型的NP难问题,对实际生产应用具有指导作用。近年来,随着遗传算法的发展,利用遗传算法来解决柔性作业车间调度问题的思想和方法层出不穷。为了促进遗传算法求解柔性作业车间调度问题的进一步发展,阐述了柔性作业车间调度问题的研究理论,对已有改进方法进行了分类,通过对现存问题的分析,探讨了未来的发展方向。     

求解柔性作业车间调度的GATOC混合方法

柔性作业车间调度问题是经典作业车间调度问题的扩展,它允许工序在可选加工机器集中任意一台上加工,加工时间随加工机器不同而不同。针对柔性作业车间调度问题的特点,提出一种基于约束理论的局部搜索方法,对关键路径上的机器的负荷率进行比较,寻找瓶颈机器,以保证各机器之间的负荷平衡。为了克服传统遗传算法早熟和收敛慢的缺点,设计多种变异操作,增加种群多样性。为了更好保留每代中的优良解,设计了基于海明距离的精英解保留策略。运用提出的算法求解基准测试问题,验证了算法的可行性和有效性。     

基于Petri网的JSP动态分类调度

以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,通过构建Petri 网控制器使系统的运行满足期望的目标,同时利用混合遗传算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等资源制约条件下的动态优化调度。为了保证生产的平稳性,最大限度地维持车间的生产能力,提出了针对不同的扰动进行分类处理的新方法,首先基于机床故障修复时间、工人离岗时间及取消订单包含任务的多少进行分类调度,然后根据机床故障修复后以及工人回岗后剩余任务的多少决定是否进行再一次的调度,最后对算法进行了仿真研究。     

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.     

Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop

Much of the research on operations scheduling problems has ignored dynamic events in real-world environments where there are complex constraints and a variety of unexpected disruptions. Besides, while most scheduling problems which have been discussed in the literature assume that machines are incessantly available, in most real life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to a scheduled preventive maintenance where the periods of unavailability are determined in advance (deterministic unavailability). This paper describes how we can integrate simulation into genetic algorithm to the dynamic scheduling of a flexible job shop with machines that suffer stochastic breakdowns. The objectives are the minimization of two criteria, expected makespan and expected mean tardiness. An overview of the flexible job shops and scheduling under the stochastic unavailability of machines are presented. Subsequently, the details of integrating simulation into genetic algorithm are described and implemented. Consequently, problems of various sizes are used to test the performance of the proposed algorithm. The results obtained reveal that the relative performance of the algorithm for both abovementioned objectives can be affected by changing the levels of the breakdown parameters.     

Scheduling the truckload operations in automated warehouses with alternative aisles for pallets

In this study, the scheduling of truck load operations in automated storage and retrieval systems is investigated. The problem is an extension of previous ones such that a pallet can be retrieved from a set of alternative aisles. It is modelled as a flexible job shop scheduling problem where the loads are considered as jobs, the pallets of a load are regarded as the operations, and the forklifts used to remove the retrieving items to the trucks are seen as machines. Minimization of maximum loading time is used as the objective to minimize the throughput time of orders and maximize the efficiency of the warehouse. A priority based genetic algorithm is presented to sequence the retrieving pallets. Permutation coding is used for encoding and a constructive algorithm generating active schedules for flexible job shop scheduling problem is applied for decoding. The proposed methodology is applied to a real problem arising in a warehouse installed by a leading supplier of automated materials handling and storage systems.     

基于Petri网的JSP动态优化调度

提出一种在柔性制造系统动态优化调度中处理紧急定单的方法。以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,对系统的设备维护、各种优先级等特性进行描述,利用遗传算法和模拟退火算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等双资源制约条件下的动态优化调度。当有紧急定单需要加工时,该方法把剩余任务和紧急任务作为两个独立的任务分别处理,然后进行集成,在紧急任务为最优调度的基础上选取剩余任务的最优调度,找到兼顾整体和局部的最优解。仿真结果说明了算法的有效性和鲁棒性。     

遗传算法求解多目标柔性Job-shop问题

本文描述了基于可变机器约束的多目标柔性Job-shop调度问题模型,并应用一种改进的遗传算法进行求解。我们采用了表示工序先后顺序及机器选择的二维编码方式,以多目标优化函数为度量,通过三种遗传操作扩展后代的多样性和算法的搜索空间。仿真结果验证了该算法能有效解决多目标优化问题。     

A heuristic for job shop scheduling to minimize total weighted tardiness

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.     

人员柔性度对作业车间调度的影响研究

针对人力资源柔性与调度效果关系研究匮乏的问题,为了揭示两者之间的量化关系,论文提出了基于资源－能力矩阵对人力资源柔性分布进行表示的方法,建立了人力资源柔性约束下的作业车间调度问题模型,采用改进遗传算法对案例进行求解。案例分析证明了人力资源柔性程度对调度效果的显著影响,这为构建柔性制造系统提供了指导意见。     

考虑多目标的柔性工艺与调度集成优化算法

针对工艺规划与车间调度集成优化问题,在考虑零件的加工工序柔性、工序次序柔性及加工机器柔性的基础上,以最大完工时间、总加工成本和总拖期时间为优化目标,对多目标柔性工艺与车间调度集成问题建模,提出一种基于改进人工蜂群算法的多目标柔性工艺与车间调度集成优化策略,并提出邻域变异操作以及全局交叉操作,对种群进行更新。引入Pareto方法,通过对适应度评价、贪婪准则、Pareto最优解集构造和保存以及解得多样性维护等方面进行改进,设计了一种基于Pareto方法的多目标人工蜂群算法。最后,通过采用基本人工蜂群算法及改进人工蜂群算法对六个工件、五台机床的柔性工艺与车间调度集成问题进行优化,验证了改进算法的有效性。     

基于遗传算法的滚动调度策略*

本文研究了动态加工环境下的一类Ｊｏｂ－Ｓｈｏｐ调度问题，提出了一种基于遗传算法的滚动调度策略，其要点是：１）借鉴预测控制的思想，采用ｔｉｍｅ－ｂａｓｅｄ和ｊｏｂ－ｂａｓｅｄ的滚动调度策略适应动态环境和要求的多变性。２）以遗传算法和分派规则相结合，处理考虑与操作序列有关的工件安装时间和工件到期时间约束的复杂调度问题。文中给出了在工件到期时间发生改变的动态环境中两种滚动调度算法的调度结果，并与静态调度     

The Machine Duplication Problem in a Job Shop with Two Jobs

This paper addresses a problem related to the classical job shop scheduling problem with two jobs. The problem consists in concurrently determining the best subset of machines to be duplicated and the optimal scheduling of the operations in order to minimize completion time. Such a problem arises in the tool management for a class of flexible manufacturing cells. The job shop with two jobs is first reviewed, the application of the classical search algorithm A* to this problem is discussed and its performance compared with a previous approach. The complexity of the machine duplication problem is then analysed. The problem is proved to be in general NP-hard in the strong sense, but in a class of special cases, relevant from the applications viewpoint, it can be solved in polynomial time by a dynamic programming algorithm. A heuristic based on such an algorithm and on A* is proposed for the general problem; the results are satisfactory in terms of both efficiency and quality of the solution.     

基于Hopfield神经网络的作业车间生产调度方法

该文提出了基于Hopfield神经网络的作业车间生产调度的新方法.文中给出了作业车 间生产调度问题(JSP)的约束条件及其换位矩阵表示,提出了新的包括所有约束条件的计算能 量函数表达式,得到相应的作业车间调度问题的Hopfield神经网络结构与权值解析表达式,并 提出相应的Hopfield神经网络作业车间调度方法.为了避免Hopfield神经网络容易收敛到局部 极小,从而产生非法调度解的缺点,将模拟退火算法应用于Hopfield神经网络求解,使Hopfield 神经网络收敛到计算能量函数的最小值0,从而保证神经网络输出是一个可行调度方案.该文 改进了已有文献中提出的作业调度问题的Hopfield神经网络方法,与已有算法相比,能够保证 神经网络稳态输出为可行的作业车间调度方案.     

基于改进的基因表达式编程算法在作业车间调度问题中的应用

文章提出一种新颖的方法一改进的基因表达式编程算法来求解作业车间调度问题。作业车间调度问题是许多实际生产调度问题的简化模型,基因表达式编程算法结合了遗传算法和遗传编程的优点,具有更强的解决问题能力,对基因表达式编程算法进行改进使其在作业车间调度问题的应用上更加有效;最后应用一个实例来验证提出方法的有效性。     

求解工件车间调度问题的一种新的邻域搜索算法

该文提出了一种新的求解工件车间调度(job shop scheduling)问题的邻域搜索算法．问题的目标是：在满足约束条件的前提下使得调度的makespan尽可能地小．定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调度结合在一起;提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向．计算了当前国际文献中的一组共58个benchmark问题实例,算法的优度高于当前国外学者提出的两种著名的先进算法．其中对18个10工件10机器的实例,包括最著名的难解实例ft10,在可接受的时间内都找到了最优解．这些实例是当前文献中报导的所有规模为10工件10机器的实例．     

Applying a hybrid job shop procedure to a Belgian manufacturing company producing industrial wheels and castors in rubber

In this paper, several methods for job shop scheduling are combined, adjusted and successfully applied to a real-world scheduling problem at a Belgian manufacturer producing industrial wheels and castors in rubber. The procedure is an extension of a hybrid shifting bottleneck procedure with a tabu search algorithm while incorporating various company specific constraints. The various extensions to cope with the company specific constraints have a strong similarity with the complex job shop problem formulation of Mason, Fowler, and Carlyle (2002). The new procedure is used as a simulation engine to test the relevance of various scenarios in order to improve the current planning approach of the company. A detailed computational experiment highlights the main contribution of the novel procedure for the company.     

遗传算法求解柔性job shop 调度问题

在分析柔性job shop调度问题特点的基础上，提出一种新的求解该问题的遗传算法，即利用编码方法表示各工序的优先调度顺序及工序的加工机器，由此产生可行的调度方案，使得问题的约束条件在染色体中得以体现．所设计的遗传算子不仅能避免非法调度解的出现，保证后代的多样性，而且可使算法具有记忆功能．仿真结果证明了该算法的有效性．     

Process plan and part routing optimization in a dynamic flexible job shop scheduling environment: an optimization via simulation approach

This paper presents an optimization via simulation approach to solve dynamic flexible job shop scheduling problems. In most real-life problems, certain operation of a part can be processed on more than one machine, which makes the considered system (i.e., job shops) flexible. On one hand, flexibility provides alternative part routings which most of the time relaxes shop floor operations. On the other hand, increased flexibility makes operation machine pairing decisions (i.e., the most suitable part routing) much more complex. This study deals with both determining the best process plan for each part and then finding the best machine for each operation in a dynamic flexible job shop scheduling environment. In this respect, a genetic algorithm approach is adapted to determine best part processing plan for each part and then select appropriate machines for each operation of each part according to the determined part processing plan. Genetic algorithm solves the optimization phase of solution methodology. Then, these machine-operation pairings are utilized by discrete-event system simulation model to estimate their performances. These two phases of the study follow each other iteratively. The goal of methodology is to find the solution that minimizes total of average flowtimes for all parts. The results reveal that optimization via simulation approach is a good way to cope with dynamic flexible job shop scheduling problems, which usually takes NP-Hard form.