混合工作日历下批量生产柔性作业车间多目标调度方法

提出了一种混合工作日历下批量生产柔性作业车间多目标调度方法。考虑设备的混合工作日历约束,构建了以生产周期最短、制造成本最低为优化目标的批量生产柔性作业车间多目标调度模型。设计了一种带精英策略的非支配排序遗传算法(NSGA II)求解该模型。算法中,采用“基于工序和设备的分段编码”方式分别对工序和设备进行编码;采用“基于工序和设备的分段交叉和变异方式”进行交叉和变异操作,采用“遗传算子改进策略”保证交叉、变异后子代个体的可行性;解码操作采用“基于平顺移动的原理”和“基于工作日历的时间推算技术”推算工序的调整开始、调整结束、加工开始和加工结束时刻。最后,通过案例分析验证了所提方法的有效性。     

Simultaneous scheduling of production and maintenance tasks in the job shop

This paper deals with the job shop problem of simultaneous scheduling of production operations and preventive maintenance tasks. To solve this problem, we develop an elitist multi-objective genetic algorithm that provides a set of Pareto optimal solutions minimising the makespan and the total maintenance cost. A deep study was made to choose the best encoding, operators, and the different probabilities. Some lower bounds of the adopted criteria are developed. The computational experiments carried out on a set of published instances validate the efficiency of the proposed algorithm.     

Energy-Aware Production Scheduling in Flow Shop and Job Shop Environments Using a Multi-Objective Genetic Algorithm

Abstract

The energy-aware scheduling problem is a multi-objective optimization problem where the main goal is to achieve energy savings without affecting productivity in a manufacturing system. In this work, we present an approach for energy-aware flow shop scheduling problem and energy-aware job shop scheduling problem considering the process speed as the main energy-related decision variable. This approach allows one to set the appropriate process speed for every considered operation in the corresponding machine. When the speed is high, the processing time is short but the energy demand increases, and vice versa. Therefore, two objectives are worked together: a production objective, paired with an energy efficiency objective. A generic elitist multi-objective genetic algorithm was implemented to solve both problems. Results from a simple comparative design of experiments and a nonparametric test show that it is possible to smooth the energy demand profile and obtain reductions that average 19.8% in energy consumption. This helps to reduce peak loads and drops on applied energy sources demand, stabilizing the conversion units operational efficiency across the entire operational time with a minimum effect on the production maximum completion time (makespan).     

基于资源限制的多目标网络计划优化模型

目前网络计划优化研究要么没有考虑资源限定的柔性,要么只是集中于单纯的工期优化或资源优化等单目标优化。本文针对传统网络计划建模资源限制缺少柔性、优化目标单一等问题进行了深入的研究。在柔性资源的限制下,为使得工程网络计划达到总体最优,考虑工程项目的工期、成本、项目净现值、资源的均衡等多个目标,建立其网络计划优化模型,并采用粒子群算法予以求解。根据拓扑排序算法生成满足时序约束的活动序列并计算活动的时间参数。对于产生资源冲突的活动,依照执行优先权解决冲突资源的执行顺序,更新时间参数。采用随机权重的方法,让粒子群算法种群的多个个体进行随机转化,从而保持解的多样性。采用国际上通用的Patterson问题库中benchmark算例对本文提出的方法进行验证。结果表明,与初始方案相比,优化后的方案分别在工期上缩减了20%,成本上缩减了11.17%,净现值增加了11.82%,资源均衡度减少了18.29%。由此可见,提出的基于粒子群算法的优化模型对资源限制下的网络计划中的工期、成本、净现值、资源均衡度等多个目标均实现了不同程度的优化。     

基于改进NSGA2算法的多目标柔性作业车间调度

柔性作业车间调度问题（FJSP）是经典作业车间调度问题的重要扩展,其中每个操作可以在多台机器上处理,反之亦然。结合实际生产过程中加工时间、机器负载、运行成本等情况,建立了多目标调度模型。针对NSGA2算法收敛性不足的缺陷,引入免疫平衡原理改进NSGA2算法的选择策略和精英保留策略,成功避免了局部收敛问题,提高了算法的优化性能。通过与启发式规则以及多种智能算法进行比对仿真实验,改进的NASA2算法能获得更好的解。用改进的NAGA2算法求解实例,不仅有效地克服多目标间数量级和量纲的障碍,而且得到了满意的pareto解集,进一步验证了该算法和模型的可行性。     

Research on rush order insertion rescheduling problem under hybrid flow shop based on NSGA-III

Rush order insertion is widespread in the enterprises that apply make-to-order production mode which affects the stability of production system. This article studies rush order insertion rescheduling problem (ROIRP) under hybrid flow shop (HFS) with multiple stages and multiple machines. A mathematical model simultaneously considering constraints such as lots, sequence-dependent set-up times and transportation times with objectives to minimise makespan, total transportation time and total machine deviation between the initial scheduling plan and the event-driven rescheduling plan is developed and NSGA-III is applied to solve the problem. Three groups of experiments are carried out which verify the suitability of NSGA-III for HFS scheduling problem with multi-objective and multi-constraint, the effectiveness of NSGA-III for the proposed ROIRP and the feasibility and effectiveness of the proposed model and algorithm in solving the ROIRP of a realistic ship pipe parts manufacturing enterprise.     

Modeling the planning and scheduling across the outsourcing supply chain: a Chaos-based fast Tabu–SA approach

Planning and Scheduling are the interrelated manufacturing functions and should be solved simultaneously to achieve the real motives of integration in manufacturing. In this paper, we have addressed the advanced integrated planning and scheduling problem in a rapidly changing environment, where the selection of outsourcing machine/operation, meeting the customers (single or multiple) due date, minimizing the makespan are the main objectives while satisfying several technological constraints. We developed a mixed integer programming model for integrated planning and scheduling across the outsourcing supply chain and showed how such models can be used to make strategic decisions. It is a computationally complex and mathematically intractable problem to solve. In this paper, a Chaos-based fast Tabu-simulated annealing (CFTSA) incorporating the features of SA, Tabu and Chaos theory is proposed and applied to solve a large number of problems with increased complexity. In CFTSA algorithm, five types of perturbation schemes are developed and Cauchy probability function is used to escape from local minima and achieve the optimal/near optimal solution in a lesser number of iterations. An intensive comparative study shows the robustness of proposed algorithm. Percentage Heuristic gap is used to show the effectiveness and two ANOVA analyses are carried out to show the consistency and accuracy of the proposed approach.     

Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method

This paper investigates an integrated bi-objective optimisation problem with non-resumable jobs for production scheduling and preventive maintenance in a two-stage hybrid flow shop with one machine on the first stage and m identical parallel machines on the second stage. Sequence-dependent set-up times and preventive maintenance (PM) on the first stage machine are considered. The scheduling objectives are to minimise the unavailability of the first stage machine and to minimise the makespan simultaneously. To solve this integrated problem, three decisions have to be made: determine the processing sequence of jobs on the first stage machine, determine whether or not to perform PM activity just after each job, and specify the processing machine of each job on the second stage. Due to the complexity of the problem, a multi-objective tabu search (MOTS) method is adapted with the implementation details. The method generates non-dominated solutions with several parallel tabu lists and Pareto dominance concept. The performance of the method is compared with that of a well-known multi-objective genetic algorithm, in terms of standard multi-objective metrics. Computational results show that the proposed MOTS yields a better approximation.     

Multi-objective integrated acyclic crew rostering and vehicle assignment problem in public bus transportation

In this study, we try to solve a real planning problem faced in public bus transportation. It is a multi-objective integrated crew rostering and vehicle assignment problem. We model this problem as a multi-objective set partitioning problem. Most of the time, crew rostering problem with a single-objective function is considered, and the output may not satisfy some transport companies. To minimize the cost and maximize the fairness of the workload among the drivers, we define many criteria. Although crew rostering problem and its integrated versions appear in the literature, it is the first time these two problems are integrated. We propose a new multi-objective tabu search algorithm to obtain near Pareto-optimal solutions. The algorithm works with a set of solutions using parallel search. We test our algorithm for the case with ten objectives and define a method to choose solutions from the approximated efficient frontier to present to the user. We discuss the performance of our meta-heuristic approach.

     

A multi-objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing

Process planning and production scheduling play important roles in manufacturing systems. In this paper we present a mixed integer linear programming (MILP) scheduling model, that is to say a slot-based multi-objective multi-product, that readily accounts for sequence-dependent preparation times (transition and set up times or machine changeover time). The proposed scheduling model becomes computationally expensive to solve for long time horizons. The aim is to find a set of high-quality trade-off solutions. This is a combinatorial optimisation problem with substantially large solution space, suggesting that it is highly difficult to find the best solutions with the exact search method. To account for this, the hybrid multi-objective simulated annealing algorithm (MOHSA) is proposed by fully utilising the capability of the exploration search and fast convergence. Two numerical experiments have been performed to demonstrate the effectiveness and robustness of the proposed algorithm.     

Multi-objective imperfect preventive maintenance optimisation with NSGA-II

Maintenance optimisation is a multi-objective problem in nature, and it usually needs to achieve a trade-off among the conflicting objectives. In this study, a multi-objective maintenance optimisation (MOMO) model is proposed for electromechanical products, where both the soft failure and hard failure are considered, and minimal repair is performed accordingly. Imperfect preventive maintenance (IPM) is carried out during the preplanned periods, and modelled with a hybrid failure rate model and quasi-renewal coefficient. The initial IPM period and the total number of IPM periods are set as the decision variables, and a MOMO model is developed to optimise the availability and cost rate concurrently. The fast elitist non-dominated sorting genetic algorithm (NSGA-II) is applied to solve the model. A case study of wind turbine’s gearbox is provided. The results show that there are 30 optimal solutions in the MOMO’s Pareto frontier that can maximise the availability and minimise the cost rate simultaneously. Compared with the single-objective maintenance optimisation, it can provide more choices for maintenance decision, and better satisfy the resource constraints and the customer’s preference. The results of the sensitivity analysis show that the effect of age reduction factor on optimisation results is greater than that of failure rate increase factor.     

Bi-objective reentrant hybrid flowshop scheduling: an iterated Pareto greedy algorithm

The multi-objective reentrant hybrid flowshop scheduling problem (RHFSP) exhibits significance in many industrial applications, but appears under-studied in the literature. In this study, an iterated Pareto greedy (IPG) algorithm is proposed to solve a RHFSP with the bi-objective of minimising makespan and total tardiness. The performance of the proposed IPG algorithm is evaluated by comparing its solutions to existing meta-heuristic algorithms on the same benchmark problem set. Experimental results show that the proposed IPG algorithm significantly outperforms the best available algorithms in terms of the convergence to optimal solutions, the diversity of solutions and the dominance of solutions. The statistical analysis manifestly shows that the proposed IPG algorithm can serve as a new benchmark approach for future research on this extremely challenging scheduling problem.     

带调整时间的多目标流水车间调度的优化算法

为高效地求解带调整时间的多目标流水车间调度问题,提出了一种多目标混合遗传算法,此算法依据基于Pareto优于关系的个体排序数和密度值计算适应度,保持解的多样性,并采用非劣解并行局部搜索策略,提高算法的搜索效率.此外,引入精英策略保证算法的收敛性,在进化过程中通过淘汰掉个别最差个体,进一步加快解的收敛速度.仿真结果表明,新算法能够有效地解决带调整时间的多目标流水车间调度问题.     

Multi-objective group scheduling optimization integrated with preventive maintenance

This article proposes a single-machine-based integration model to meet the requirements of production scheduling and preventive maintenance in group production. To describe the production for identical/similar and different jobs, this integrated model considers the learning and forgetting effects. Based on machine degradation, the deterioration effect is also considered. Moreover, perfect maintenance and minimal repair are adopted in this integrated model. The multi-objective of minimizing total completion time and maintenance cost is taken to meet the dual requirements of delivery date and cost. Finally, a genetic algorithm is developed to solve this optimization model, and the computation results demonstrate that this integrated model is effective and reliable.     

A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems

This study considers the problem of job scheduling on unrelated parallel machines. A multi-objective multi-point simulated annealing (MOMSA) algorithm was proposed for solving this problem by simultaneously minimising makespan, total weighted completion time and total weighted tardiness. To assess the performance of the proposed heuristic and compare it with that of several benchmark heuristics, the obtained sets of non-dominated solutions were assessed using four multi-objective performance indicators. The computational results demonstrated that the proposed heuristic markedly outperformed the benchmark heuristics in terms of the four performance indicators. The proposed MOMSA algorithm can provide a new benchmark for future research related to the unrelated parallel machine scheduling problem addressed in this study.     

Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints

In this paper, a three-stage assembly flow shop scheduling problem with machine availability constraints is taken into account. Two objectives of minimising total weighted completion times (flow time) and minimising sum of weighted tardiness and earliness are simultaneously considered. To describe this problem, a mathematical model is presented. The problem is generalisation of three-machine flow shop scheduling problem and two-stage assembly flow shop scheduling problem. Since these problems are known to be NP-hard, the considered problem is also strongly NP-hard. Therefore, two multi-objective meta-heuristics are presented to efficiently solve this problem in a reasonable amount of time. Comprehensive computational experiments are performed to illustrate the performance of the presented algorithms.     

混合流程型企业主生产计划的启发式算法

提出了一个新的启发式算法,该启发式算法称为多目标主生产计划算法(MOMPS),用于解决混合流水线车间的主生产计划安排,该启发式算法主要有以下目标:最小化拖期惩罚,最小化完工时间,最小化装设和库存成本等.该算法先对所有的定单进行排序,然后根据最小生产成本树及其该树的最大生产能力进行定单的分配,如果定单数量超出了最大生产能力,对生产网络进行调整,通过比较次优生产成本树和拖期以后的最小生产成本决定定单是否该拖期.最后通过和一般的线性规划进行比较,得出该算法在解决混合流程型企业的多目标主生产计划的制定中十分有效,有时得到的结果和线性规划模型解出的解是一致的.     

Multi-threaded simulated annealing for a bi-objective maintenance scheduling problem

A parallel Simulated Annealing algorithm with multi-threaded architecture is proposed to solve a real bi-objective maintenance scheduling problem with conflicting objectives: the minimisation of the total equipment downtime caused by maintenance jobs and the minimisation of the multi-skilled workforce requirements over the given horizon. The maintenance jobs have different priorities with some precedence relations between different skills. The total weighted flow time is used as a scheduling criterion to measure the equipment availability. The multi-threaded architecture is used to speed up a multi-objective Simulated Annealing algorithm to solve the considered problem. Multi-threading is a form of parallelism based on shared memory architecture where multiple logical processing units, so-called threads, run concurrently and communicate via shared memory. The performance of the parallel method compared to the exact method is verified using a number of test problems. The obtained results imply the high efficiency and robustness of the proposed heuristic for both solution quality and computational effort.     

A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems

This paper presents a hybrid Pareto-based local search (PLS) algorithm for solving the multi-objective flexible job shop scheduling problem. Three minimisation objectives are considered simultaneously, i.e. the maximum completion time (makespan), the total workload of all machines, and the workload of the critical machine. In this study, several well-designed neighbouring approaches are proposed, which consider the problem characteristics and thus can hold fast convergence ability while keep the population with a certain level of quality and diversity. Moreover, a variable neighbourhood search (VNS) based self-adaptive strategy is embedded in the hybrid algorithm to utilise the neighbouring approaches efficiently. Then, an external Pareto archive is developed to record the non-dominated solutions found so far. In addition, a speed-up method is devised to update the Pareto archive set. Experimental results on several well-known benchmarks show the efficiency of the proposed hybrid algorithm. It is concluded that the PLS algorithm is superior to the very recent algorithms, in term of both search quality and computational efficiency.     

An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time

With the increasing attention on environment issues, green scheduling in manufacturing industry has been a hot research topic. As a typical scheduling problem, permutation flow shop scheduling has gained deep research, but the practical case that considers both setup and transportation times still has rare research. This paper addresses the energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time to minimise both makespan as economic objective and energy consumption as green objective. The mathematical model of the problem is formulated. To solve such a bi-objective problem effectively, an improved multi-objective evolutionary algorithm based on decomposition is proposed. With decomposition strategy, the problem is decomposed into several sub-problems. In each generation, a dynamic strategy is designed to mate the solutions corresponding to the sub-problems. After analysing the properties of the problem, two heuristics to generate new solutions with smaller total setup times are proposed for designing local intensification to improve exploitation ability. Computational tests are carried out by using the instances both from a real-world manufacturing enterprise and generated randomly with larger sizes. The comparisons show that dynamic mating strategy and local intensification are effective in improving performances and the proposed algorithm is more effective than the existing algorithms.