GA based heuristic for the open job shop scheduling problem

Open job shop scheduling is a kind of job shop scheduling in which operations can be performed in any order. In this paper an attempt is made to develop a heuristic for the open job shop scheduling problem using genetic algorithm to minimize makespan. Genetic algorithm operators are suitably modified to maintain feasibility. The results are statistically compared and found to be significantly better than the earlier reported results.     

MES的计划、调度集成问题研究

在分析制造执行系统(Manufacturing Executive System(MES))产生的背景、概念及其特点的基础上，构造了先进制造车间(Advanced Manufacturing Shopfloor(AMS))计划调度问题的集成功能模型。结合此模型，建立了AMS的作业分批与计划调度的数学模型，并在最后给出了求解此类问题的常用算法。     

A multiobjective genetic algorithm for scheduling a flexible manufacturing system

Though the designers of Flexible Manufacturing Systems (FMS) strive to ensure the maximum flexibility in the system, in practice, after the implementation of such systems the operational executives often find it hard to accommodate frequent variations in the part designs of incoming jobs. This difficulty can very well be overcome by scheduling the variety of incoming parts into the system efficiently. In this work an appropriate scheduling mechanism is designed to generate a nearer-to-optimum schedule using Genetic Algorithm (GA) with two different GA Coding Schemes. Two contradictory objectives of the system were achieved simultaneously by the scheduling mechanism. The results are compared with those obtained by different scheduling rules and conclusions are presented.     

钢铁企业先进生产计划和实时生产调度技术的研究

为了解决钢铁企业目前由于缺乏生产计划和调度系统而造成的宏观调控和实时监控等方面存在的问题，在对现有钢铁企业的信息化体系结构和生产管理模式等进行理论研究的基础上，提出了基于MRP II与JIT相结合的特钢行业生产管理模式；采用多层递阶计划和动态实时调度策略，构建面向企业上层管理ERP和下层执行MES系统的集成化解决方案。实现了企业生产计划和调度的整体优化，建立了适合特钢企业经营管理与生产制造一体化的信息系统。     

Crowding-measure-based multiobjective evolutionary algorithm for job shop scheduling

Multiobjective evolutionary algorithm (MOEA) has attracted much attention in the past decade; however, the application of MOEA to practical problems such as job shop scheduling is seldom considered. In this paper, crowding-measure-based multiobjective evolutionary algorithm (CMOEA) is first designed, which makes use of the crowding measure to adjust the external population and assign different fitness for individuals; then CMOEA is applied to job shop scheduling to minimize makespan and the total tardiness of jobs. Finally, the comparison between CMOEA and SPEA demonstrates that CMOEA performs well in job shop scheduling.     

考虑装配及运输环节的工艺计划与调度问题

针对工艺规划与调度集成问题在制造环节方面考虑的不足,将制造环节从仅考虑工件制造扩展到由工件制造、组件装配及完成件装配组成的完整制造过程。考虑到加工设备可能属于不同的车间,将运输环节考虑到制造过程中。提出一种考虑装配及运输环节的工艺规划与调度集成问题,以完工时间为优化目标对该问题进行数学建模。为有效压缩搜索域,设计了一种带优选策略的粒子群算法对该问题进行求解。通过实例验证了该数学模型的正确性及算法的有效性。     

Optimization of multi-objective integrated process planning and scheduling problem using a priority based optimization algorithm

For increasing the overall performance of modern manufacturing systems, effective integration of process planning and scheduling functions has been an important area of consideration among researchers. Owing to the complexity of handling process planning and scheduling simultaneously, most of the research work has been limited to solving the integrated process planning and scheduling (IPPS) problem for a single objective function. As there are many conflicting objectives when dealing with process planning and scheduling, real world problems cannot be fully captured considering only a single objective for optimization. Therefore considering multi-objective IPPS (MOIPPS) problem is inevitable. Unfortunately, only a handful of research papers are available on solving MOIPPS problem. In this paper, an optimization algorithm for solving MOIPPS problem is presented. The proposed algorithm uses a set of dispatching rules coupled with priority assignment to optimize the IPPS problem for various objectives like makespan, total machine load, total tardiness, etc. A fixed sized external archive coupled with a crowding distance mechanism is used to store and maintain the non-dominated solutions. To compare the results with other algorithms, a C-matric based method has been used. Instances from four recent papers have been solved to demonstrate the effectiveness of the proposed algorithm. The experimental results show that the proposed method is an efficient approach for solving the MOIPPS problem.     

A hybrid genetic algorithm for integrated process planning and scheduling problem with precedence constraints

Process planning and scheduling are two important functions in a modern manufacturing system. Although integrating decisions related to these functions gives rise to a hard combinatorial problem, due to the impressive improvement in system performance which is resulted through this integration, developing effective methods to solve this problem is of great theoretical and practical importance. In this research, after formulating the integrated process planning and scheduling problem as a mathematical program, we propose a hybrid genetic algorithm (GA) for the problem. In the proposed algorithm, problem-specific genetic operators are designed to enhance the global search power of GA. Also, a local search procedure has been incorporated into the GA to improve the performance of the algorithm. The model considers precedence relations among job operations, based on which feasible process plans for each job can be represented implicitly. A novel neighborhood function, considering the constraints of a flexible job shop environment and nonlinear precedence relations among operations, is presented to speed up the local search process. In experimental study, the performance of the proposed algorithm has been evaluated based on a number of problems adopted from the literature. The experimental results demonstrate the efficiency of the proposed algorithm to find optimal or near-optimal solutions.     

基于混合整数规划的高级计划排程方法研究

针对目前离散制造企业普遍存在的MRP计划和车间调度相脱节的问题,本文提出了高级计划排程(APS)的数学模型和近似求解算法。以订单的提前/拖期总惩罚成本最小为目标函数,构建了包含BOM结构、零件加工次序、机器析取约束等的APS混合整数规划模型;采用遗传算法对APS模型进行近似求解,该算法采用随机键编码方式、轮盘赌选择方法、两点交叉法、精英保留策略等遗传操作;最后用算例验证了APS模型和求解方法的有效性。     

一类并行机调度问题的动态调度算法

针对不确定制造环境中配件数量约束条件发生变化后的并行机动态调度问题,提出了一种基于操作属性模式的并行机动态调度算法.该算法针对总拖期时间性能指标的优化,根据配件负载的裕量和相邻操作的属性模式,对原调度方案的操作次序和操作上机时间进行了调整.在不同操作和设备规模下,以及不同配件数量变化幅度下进行了数值计算.数值计算结果和实际应用结果表明,该算法是有效的,具有计算复杂度低、实时性好、对原调度算法不敏感的特点.     

大批量柔性制造模式下光伏行业高级计划排程策略研究

本文深度调研了光伏行业太阳能电池片生产工艺和生产组织方式,在研究分析各生产类型计划排产特点的基础上,提出了一种大批量柔性制造模式下的APS高级计划排产策略,基于J2EE企业级应用开发规范,采用最新的Web技术和JAVA开发语言,设计开发了大批量柔性制造高级计划排程系统.     

Integrated optimization of production planning and scheduling for a kind of job-shop

This paper addresses an integrated job-shop production planning and scheduling problem with setup time and batches. It not only considers the setup cost, work-in-process inventory, product demand, and the load of equipment, but also the detailed scheduling constraints. That is a way different from the traditional hierarchical production planning method. The hierarchical methods do not consider the detailed scheduling constraints, so it cannot guarantee to obtain a feasible production plan. Here the integrated problem is formulated as a nonlinear mixed integer program model. And in order to simultaneously optimize the production plan and the schedule, an improved hybrid genetic algorithm (HGA) is given. In the model, the detailed scheduling constraints are used to compute the accurate load of a device in order to obtain a feasible production plan. The heuristic scheduling rules such as the shortest processing time (SPT) and the longest processing time (LPT) are used to generate a better initial solution. Also, a subsection coding strategy is offered to convert the planning and scheduling solution into a chromosome. At last, a comparison is made between the hybrid algorithm and a hierarchical production planning and scheduling method, showing that the hybrid algorithm can solve the problem effectively.     

订单型企业多目标生产计划的制定及其调度

针对制定订单式小批量生产计划问题,提出了一种使用动态随机投入产出函数来制定多目标生产计划的方法。针对生产调度问题,提出了联合使用最长加工时间优先(LPT)与遗传算法(GA)的混合遗传算法(HGA)来求解混合流水线的调度,并给出了一种新的编码方法,选择了相应的交叉和变异方法。研究结果表明,该计划制造方法能较好地满足订单型企业的随机性要求,而且生产计划编制效率高。该编码方法在保证染色体合法性的同时也保证了算法本身的随机性。某轧辊厂的实际案例分析结果也验证了所提出的订单型企业多目标生产计划的制定及其调度方法的可行性。     

A hybrid cuckoo search and variable neighborhood descent for single and multiobjective scheduling problems

Cuckoo search (CS) is a relatively new meta-heuristic that has proven its strength in solving continuous optimization problems. This papers applies cuckoo search to the class of sequencing problems by hybridizing it with a variable neighborhood descent local search for enhancing the quality of the obtained solutions. The Lévy flight operator proposed in the original CS is modified to address the discrete nature of scheduling problems. Two well-known problems are used to demonstrate the effectiveness of the proposed hybrid CS approach. The first is the NP-hard single objective problem of minimizing the weighted total tardiness time ( \(1|| \sum {T_{w}}\) ) and the second is the multiobjective problem of minimizing the flowtime \(\overline {C}\) and the maximum tardiness T _{m a x} for single machine ( \(1|| (\frac {1}{n}\sum {C}, T_{max})\) ). For the first problem, computational results show that the hybrid CS is able to find the optimal solutions for all benchmark test instances with 40, 50, and 100 jobs and for most instances with 150, 200, 250, and 300 jobs. For the second problem, the hybrid CS generated solutions on and very close to the exact Pareto fronts of test instances with 10, 20, 30, and 40 jobs. In general, the results reveal that the hybrid CS is an adequate and robust method for tackling single and multiobjective scheduling problems.     

一类两阶段生产系统生产计划与调度的集成优化

针对传统生产计划与调度制定中存在的不足,研究了一类两阶段生产系统的生产计划与调度集成优化问题。建立了能够反映生产计划与调度相互关联特点的离散双层规划模型,提出一种基于混合优化方法的分支定界解法以及有效缩减搜索空间的方法,并构造了有效下界。针对分支定界法的松弛问题,给出采用模拟退火算法与预估校正法交替迭代求解的混合优化方法。通过实验仿真,验证了模型与算法的有效性。     

遗传算法在多品种装配生产排序中的应用

针对多品种装配顺序的安排问题,以总工艺辅助时间最小为目标,表达为求解旅行商问题(TSP),提出并设计了合理的遗传算法。计算和仿真结果显示,该遗传算法的实用性和有效性。     

求解分布式混合流水线调度问题的改进双层嵌套式遗传算法

针对分布式混合流水线生产的生产调度问题,模拟实际排产中的排产到线和排产到时的排产策略,提出了基于改进双层嵌套式遗传算法的两层优化模型。外层依据流水线分配平衡和准时交货等基本原则总体上解决生产订单在流水线之间的分配问题,内层以最小生产时间为主要目的求解流水线的生产订单生产次序问题。考虑到双层嵌套式遗传算法的时间复杂性,基于模糊逻辑理论设计了一种模糊控制器来动态调整遗传算子,并采用主动检测停止方法,提高算法效率。使用某空调工厂的实际生产数据验证了算法的可行性、计算结果的准确性及排产策略的有效性,为高级计划与排程(Advanced Planning and Scheduling,APS)中大规模复杂供应链调度问题提供了可借鉴的方法。     

Solution approaches for a real-life resource-constrained parallel machine scheduling problem

This paper deals with a real-world scheduling problem in an injection-molding department of an electrical appliance plant. In the department, a resource-constrained parallel machine scheduling problem with machine eligibility restrictions is investigated. First, an integer-programming (IP) model with the objective of minimizing makespan is developed for the entire problem. Since this entire IP model has a huge number of variables, it cannot handle the problem efficiently. To obtain more efficient results, two solution approaches, namely IP/IP and IP/constraint programming (CP) both of which partition the entire problem into loading and scheduling sub-problems, are proposed. The loading phase, in which an IP loading model assigns the jobs to machines with the aim of minimizing maximum load on the machines and operators, is the same for both approaches. Subsequently, in the scheduling phase, the IP/IP approach uses an IP scheduling model while the IP/CP approach applies a CP scheduling model to obtain the final schedule of the jobs. Computational results show that the proposed solution methods improve makespan values for almost all test problems in comparison to the entire IP model. In particular, the IP/IP approach performs better in the test problems with greater number of operators, whereas IP/CP approach provides quick and practical results in almost all test problems and gives relatively more efficient makespan values when the resource constraints are tight (i.e., the case of smaller number of operators).