An improved genetic algorithm for integrated process planning and scheduling

Process planning and scheduling are two of the most important functions involved in manufacturing process and they are actually interrelated; integration of the two is essential to improve the flexibility of scheduling and achieve a global improvement for the performance of a manufacturing system. In order to facilitate the optimization of process planning and scheduling simultaneously, a mathematical model for the integrated process planning and scheduling (IPPS) is established, and an improved genetic algorithm (IGA) is proposed for the problem. For the performance improvement of the algorithm, new initial selection method for process plans, new genetic representations for the scheduling plan combined with process plans and genetic operator method are developed. To verify the feasibility and performance of the proposed approach, experimental studies are conducted and comparisons are made between this approach and others with the makespan and mean flow time performance measures. The results show that the proposed approach on IPPS has achieved significant improvement in minimizing makespan and obtained good results for the mean flow time performance measure with high efficiency.     

基于混沌粒子群算法的单台批加工设备调度

提出了一种基于混沌粒子群算法的双层调度方法。双层调度的外层基于加工时间最小的目标构建组批方法集,然后将其作为内层算法的搜索空间;双层调度的内层以加工时间最小为适应值函数,采用混沌粒子群算法求解批次排序的最优解,得到最优的组批方法及其排序。通过仿真验证了该算法在搜索时间和搜索精度的可行性。     

成批生产计划调度的集成建模与优化

针对多品种批量生产类型,建立了调度约束的生产计划与调度集成优化模型。模型的目标函数是使总调整费用、库存费用及生产费用之和最小,约束函数包括库存平衡约束和生产能力约束,同时考虑了调度约束,即工序顺序约束和工件在单机上的加工能力约束,保证了计划可行性。该模型为两层混合整数规划模型,对其求解综合运用了遗传算法和启发式规则,提出了混合启发式求解算法。最后,针对某机床厂多品种批量生产类型车间进行了实例应用,对车间零件月份作业计划进行分解,得到各工段单元零件周作业计划,确定了零件各周生产批量与投产顺序。     

A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks

In simple flow shop problems, each machine operation center includes just one machine. If at least one machine center includes more than one machine, the scheduling problem becomes a flexible flow shop problem (FFSP). Flexible flow shops are thus generalization of simple flow shops. Flexible flow shop scheduling problems have a special structure combining some elements of both the flow shop and the parallel machine scheduling problems. FFSP can be stated as finding a schedule for a general task graph to execute on a multiprocessor system so that the schedule length can be minimized. FFSP is known to be NP-hard. In this study, we present a particle swarm optimization (PSO) algorithm to solve FFSP. PSO is an effective algorithm which gives quality solutions in a reasonable computational time and consists of less numbers parameters as compared to the other evolutionary metaheuristics. Mutation, a commonly used operator in genetic algorithm, has been introduced in PSO so that trapping of solutions at local minima or premature convergence can be avoided. Logistic mapping is used to generate chaotic numbers in this paper. Use of chaotic numbers makes the algorithm converge fast towards near-optimal solution and hence reduce computational efforts further. The performance of schedules is evaluated in terms of total completion time or makespan (C_max). The results are presented in terms of percentage deviation (PD) of the solution from the lower bound. The results are compared with different versions of genetic algorithm (GA) used for the purpose from open literature. The results indicate that the proposed PSO algorithm is quite effective in reducing makespan because average PD is observed as 2.961, whereas GA results in average percentage deviation of 3.559. Finally, influence of various PSO parameters on solution quality has been investigated.     

Multi-objective integrated optimization research on preventive maintenance planning and production scheduling for a single machine

Preventive maintenance (PM) planning and production scheduling are among the most important problems in the manufacturing industries. Researchers have begun to investigate the integrated optimization problem of PM and production scheduling with a single objective. However, many industries have trade-offs in their scheduling problems where multiple objectives must be considered in order to optimize the overall performance of the system. In this paper, five objectives, including minimizing maintenance cost, makespan, total weighted completion time of jobs, total weighted tardiness, and maximizing machine availability are simultaneously considered to optimize the integrated problem of PM and production scheduling introduced by Cassady and Kutanoglu. Multi-objective genetic algorithm (MOGA) is used to solve the integrated optimization problem. To illuminate the conflicting nature of the objective functions, decision-makers’ preferences of the multiple objectives are not integrated into the MOGA. The total weighted percent deviation, which represents not only the preferences of the objectives but also the deviations of the solutions, is proposed to help decision-makers select the best solution among the near-Pareto optimal solutions obtained by the MOGA. A numerical example reveals the necessity and significance of integrating optimization of PM and production scheduling considering multiple objectives.     

基于动态机器故障率的并联加工系统资源多目标调度

针对并联加工系统,为处理生产过程中因机器故障导致的加工资源动态调度问题,考虑系统资源负荷和故障率存在的动态相互制约关系,依据子周期划分的不同策略,对调度后的加工总时间、预防维修时间和系统可靠度进行量化研究,构建多目标动态调度模型。采用基于Pareto熵的多目标粒子群算法对模型进行求解,通过改进个体最优解选择策略,提升最优解选取的多样性;通过差熵来估计种群所处进化状态,改进算法的搜索能力。以某企业的加工系统为实例,利用该模型进行加工资源调度方案设计,通过模糊决策得到的多目标权重,选取最优调度方案,并进行多个参数对比,验证在加工资源调度过程中,集成考虑动态机器故障率和基于机器最大役龄约束划分子周期的可行性,不仅可以完成订单准时交付,还可以使企业有更好的柔性去应对可能到来的紧急订单。     

Reentrant two-stage multiprocessor flow shop scheduling with due windows

Reentrant flow shop scheduling allows a job to revisit a particular machine several times. The topic has received considerable interest in recent years; with related studies demonstrating that particle swarm algorithm (PSO) is an effective and efficient means of solving scheduling problems. By selecting a wafer testing process with the due window problem as a case study, this study develops a farness particle swarm optimization algorithm (FPSO) to solve reentrant two-stage multiprocessor flow shop scheduling problems in order to minimize earliness and tardiness. Computational results indicate that either small- or large-scale problems are involved in which FPSO outperforms PSO and ant colony optimization with respect to effectiveness and robustness. Importantly, this study demonstrates that FPSO can solve such a complex scheduling problem efficiently.     

Bottleneck identification procedures for the job shop scheduling problem with applications to genetic algorithms

Two bottleneck identification algorithms (one for bottleneck machines and the other for bottleneck jobs) are presented for the job shop scheduling problem in which the total weighted tardiness must be minimized. The scheduling policies on bottleneck machines can have significant impact on the final scheduling performance, and therefore, they need to be optimized with more computational effort. Meanwhile, bottleneck jobs that can cause considerable deterioration to the solution quality also need to be considered with higher priority. In order to describe the characteristic information concerning such bottleneck machines and bottleneck jobs, a statistical approach is devised to obtain the bottleneck characteristic values for each machine, and, in addition, a fuzzy inference system is employed to transform human knowledge into the bottleneck characteristic values for each job. These bottleneck characteristic values reflect the features of both the objective function and the current optimization stage. Finally, the effectiveness of the two procedures is verified by specifically designed genetic algorithms.     

An effective hybrid particle swarm optimization for no-wait flow shop scheduling

The no-wait flow shop scheduling that requires jobs to be processed without interruption between consecutive machines is a typical NP-hard combinatorial optimization problem, and represents an important area in production scheduling. This paper proposes an effective hybrid algorithm based on particle swarm optimization (PSO) for no-wait flow shop scheduling with the criterion to minimize the maximum completion time (makespan). In the algorithm, a novel encoding scheme based on random key representation is developed, and an efficient population initialization, an effective local search based on the Nawaz-Enscore-Ham (NEH) heuristic, as well as a local search based on simulated annealing (SA) with an adaptive meta-Lamarckian learning strategy are proposed and incorporated into PSO. Simulation results based on well-known benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed hybrid algorithm.     

基于改进粒子群算法的车间作业排序的优化设计

兼顾车间作业排序中的制造周期和机器利用率,建立了以最小化最大完工时间为主目标、以最大化机器利用率为从目标的优化模型。设计了引入自适应技术的惯性权重,使基本粒子群算法的学习因子可动态变化地改进粒子群算法,并用该改进后的算法对车间作业排序进行了优化设计。实例研究表明：改进后的粒子群算法在收敛速度和收敛可靠性上均优于未改进的粒子群算法,在求解车间作业排序问题的应用中具有更高的求解质量。     

Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing

In this paper, we address a scheduling problem for minimizing total weighted flowtime, observed in automobile gear manufacturing. Specifically, the bottleneck operation of the pre-heat treatment stage of gear manufacturing process has been dealt with in scheduling. Many real-life scenarios like unequal release times, sequence dependent setup times, and machine eligibility restrictions have been considered. A mathematical model taking into account dynamic starting conditions has been proposed. The problem is derived to be NP-hard. To approach the problem, a few heuristic algorithms have been proposed. Based on planned computational experiments, the performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small-size problem instances and (b) in comparison with the estimated optimal solution for large-size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently yielding near-statistically estimated optimal solutions in a reasonable computational time.     

[生产计划]动态制造系统生产计划与调度协同优化

基于生产计划与调度协同优化的思路,建立了计划与调度滚动优化模型,并提出一种 “闭环集成滚动重调度”策略。当生产系统出现产能受限或订单变更等动态变化时,调度与计划形成“闭环响应模式”,进而采用动态约束平衡的混合算法对生产计划与调度进行协同优化。为验证所提出协同优化策略的有效性和可行性,选取典型算例进行了仿真研究,结果表明该策略能有效处理生产系统的动态变化,保证系统的调度优化及时调整。     

[工艺规划与装配线平衡]两阶段混合算法求解集成工艺规划与调度问题

提出了求解集成式工艺规划与车间调度问题的两阶段混合算法。在工艺规划阶段,使用遗传算法为每个工件生成可选的近优工艺路线集,动态地为车间调度阶段输入已确定的工艺路线;在车间调度阶段,使用蜜蜂交配优化算法快速寻优,设计了蜂王婚飞的流程以保证算法的全局搜索能力,构建了基于不同邻域结构的工蜂培育幼蜂局部搜索策略。使用基准测试集对提出的方法进行验证,并与现有算法进行对比,计算结果证明了提出方法的有效性。     

A hybrid particle swarm optimization for parallel machine total tardiness scheduling

The parallel machine scheduling problem has received increasing attention in recent years. This research considers the problem of scheduling jobs on parallel machines with a total tardiness objective. In the view of its non-deterministic polynomial-time hard nature, the particle swarm optimization (PSO), which is inspired by the swarming or collaborative behavior of biological populations, is employed to solve the parallel machine total tardiness problem (PMTP). Since it is very hard to directly apply standard PSO to this problem, a new solution representation is designed based on real number encoding, which can conveniently convert the job sequences of PMTP to continuous position values. Moreover, in order to enhance the performance of PSO, we introduce clonal selection algorithm (CSA) into PSO and therefore propose a new CSPSO method. The incorporation of CSA can greatly improve the swarm diversity and avoid premature convergence. We further investigate three parameters of PSO and CSPSO, finding that the parameters have marginal impact on CSPSO, which indicates that CSPSO is a very stable and robust method. The performance of CSPSO is evaluated in comparison with traditional genetic algorithm (GA) and standard PSO on 250 benchmark instances. Experimental results show that CSPSO significantly outperforms GA and PSO, with obtaining the optimal solutions of 237 instances. Additionally, PSO appears more effective than GA.     

Optimization of process planning with various flexibilities using an imperialist competitive algorithm

In this paper, we investigate the optimization of process planning in which various flexibilities are considered. The objective is to minimize total weighted sum of manufacturing costs. Various flexibilities, including process flexibility, sequence flexibility, machine flexibility, tool flexibility, and tool access direction (TAD) flexibility, generally exist in process planning and consideration of these flexibilities is essential for improving production efficiency and system flexibility. However, process planning is strongly NP-hard due to the existence of various flexibilities as well as complex machining precedence constraints. To tackle this problem, an imperialist competitive algorithm (ICA) is employed to find promising solutions with reasonable computational cost. ICA is a novel socio-politically motivated metaheuristic algorithm inspired by imperialist competition. It starts with an initial population and proceeds through assimilation, position exchange, imperialistic competition, and elimination. Computational experiments on three sets of process planning problem taken from literature are carried out, and comparisons with some existing algorithms developed for process planning are presented. The results show that the algorithm performs significantly better than existing algorithms like genetic algorithm (GA), simulated annealing (SA), tabu search (TS), and particle swarm optimization (PSO).     

基于改进禁忌搜索算法的单机成组作业调度

提出了单机作业调度的改进禁忌搜索算法。以总流程时间最短为优化目标的具有作业分类与机器设置时间的单机成组作业高度问题是NP难问题,此问题的多项式求解方法不能保证求取最优解。基于改进禁忌搜索算法,建立了具有提交时间与分类设置时间的单机成组作业调度模型,可搜索到该问题的最优解。仿真实验表明,改进禁忌搜索算法能够搜索到最优解,其性能优于WSPT启发式算法,并且运行时间短,可应用于大规模调度问题。     

基于约束理论的混合复杂流水线规划调度算法

针对可重入、批处理、准备时间长以及多目标混合流水生产线问题,给出了复杂生产线的一般描述,提出了一种基于约束理论的规划调度算法。整个算法框架建立在约束理论五步原则基础上,并通过目标规划的思想实现了多目标优化,为了验证算法解决复杂性的能力,通过估算瓶颈能力给出了生产线的上界以作比较。     

Bi-objective hybrid flow shop scheduling: a new local search

In this paper, we have considered the bi-objective hybrid flow shop scheduling problem with the objectives of minimizing makespan and minimizing total tardiness. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally, and hence, heuristics are used to obtain good solutions in a reasonable time. On the other hand, local search is a method for solving computationally hard optimization problems. Hence, we introduce a novel bi-objective local search algorithm (BOLS) to solve the problem efficiently. This local search can perform an effective search in three phases. In the initial phase, the assigned job set of a machine is moved to other machines. In the second phase, the order of jobs is changed for a machine. Finally, in phase 3, a process is done to change the assigned job set of a machine and order of jobs for a machine simultaneously. A measure of performance in literature namely free disposal hull approach and a new technique proposed by authors called “triangle method” have been used to evaluate the quality of the obtained solutions. The experimental results of the comparison between the proposed algorithm and several effective algorithms show that the BOLS is attractive for solving the bi-objective scheduling problem.     

A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time

This paper proposes a particle swarm optimization (PSO) algorithm based on memetic algorithm (MA) that hybridizes with a local search method for solving a no-wait flow shop scheduling problem. The main objective is to minimize the total flow time. Within the framework of the proposed algorithm, a local version of PSO with a ring-shape topology structure is used as global search. In addition, a self-organized random immigrant's scheme is extended into our proposed algorithm in order to further enhance its exploration capacity for new peaks in search space. The experimental study over the moving peaks benchmark problem shows that the proposed PSO-based MA is robust. Finally, the analysis of the computational results and conclusion are given.     

Single-machine-based production scheduling model integrated preventive maintenance planning

Manufacturing and production plants operate physical machine that will deteriorate with increased usage and time. Maintenance planning which can keep machines in good operation is thus required for smooth production. However, in previous research, production scheduling and maintenance planning are usually performed individually and not studied as an integrated model. In order to balance the trade-offs between them, this study proposes an integrated scheduling model by incorporating both production scheduling and preventive maintenance planning for a single-machine problem with the objective of minimizing the maximum weighted tardiness. In this model, a variable maintenance time subjected to machine degradation is considered. Finally, a numerical example using this improved production scheduling model is shown. The computational results prove its efficiency.