Hybrid evolutionary algorithm for no-wait flow shops to minimize makespan and total flowtime

The NP-hard no-wait flow shop scheduling problems with makespan and total flowtime minimization are considered. Objective increment properties of the problems are analyzed. A non-dominated classification method is introduced to class population individuals into Pareto fronts to improve searching efficiency. Besides investigating the crowding distance and the elitist solution strategy, two effective bi-criteria local search procedures based on objective increments are presented to improve searching effectiveness. Based on the properties and methods, a hybrid evolutionary algorithm is proposed for the considered problems and compared with the best existing algorithms. Experimental results show that the proposed algorithm is effective with high efficiency.

Heuristic for no-wait flow shops with makespan minimization based on total idle-time increments

No-wait flow shops with makespan minimization are classified as NP-hard. In this paper, the optimization objective is equivalently transformed to total idle-time minimization. The independence relationship between tasks is analyzed, and objective increment properties are established for the fundamental operators of the heuristics. The quality of the new schedules generated during a heuristic is judged only by objective increments and not by the traditional method, which computes and compares the objective of a whole schedule. Based on objective increments, the time complexity of the heuristic can be decreased by one order. A seed phase is presented to generate an initial solution according to the transformed objective. Construction and improvement phases are introduced by experimental analysis. The FCH （fast composite heuristic） is proposed and compared with the most effective algorithms currently available for the considered problem. Experimental results show that the effectiveness of the FCH is similar to that of the best methods but requires far less computation time. The FCH can also be efficient in real time scheduling and rescheduling for no-wait flow shops.

Scheduling on 2-Machine Flow Shops Considering Disturbance on Job Processing Times

In this paper the scheduling problem to minimize the expected makespan is discussed on two-machine flow shops with random disturbance on job processing times. The problem is represented by a stochastic programming model. We approximate the stochastic problem by a deterministic problem which can be solved by Johnson's rule. The estimation of approximation error is also discussed by analyzing the stochastic model and its approximate LP model.

Q-Learning-Assisted Meta-Heuristics for Scheduling Distributed Hybrid Flow Shop Problems

The flow shop scheduling problem is important for the manufacturing industry.Effective flow shop scheduling can bring great benefits to the industry.However,there are few types of research on Distributed Hybrid Flow Shop Problems(DHFSP)by learning assisted meta-heuristics.This work addresses a DHFSP with minimizing the maximum completion time(Makespan).First,a mathematical model is developed for the concerned DHFSP.Second,four Q-learning-assisted meta-heuristics,e.g.,genetic algorithm(GA),artificial bee colony algorithm(ABC),particle swarm optimization(PSO),and differential evolution(DE),are proposed.According to the nature of DHFSP,six local search operations are designed for finding high-quality solutions in local space.Instead of randomselection,Q-learning assists meta-heuristics in choosing the appropriate local search operations during iterations.Finally,based on 60 cases,comprehensive numerical experiments are conducted to assess the effectiveness of the proposed algorithms.The experimental results and discussions prove that using Q-learning to select appropriate local search operations is more effective than the random strategy.To verify the competitiveness of the Q-learning assistedmeta-heuristics,they are compared with the improved iterated greedy algorithm(IIG),which is also for solving DHFSP.The Friedman test is executed on the results by five algorithms.It is concluded that the performance of four Q-learning-assisted meta-heuristics are better than IIG,and the Q-learning-assisted PSO shows the best competitiveness.

An Elite-Class Teaching-Learning-Based Optimization for Reentrant Hybrid Flow Shop Scheduling with Bottleneck Stage

Bottleneck stage and reentrance often exist in real-life manufacturing processes;however,the previous research rarely addresses these two processing conditions in a scheduling problem.In this study,a reentrant hybrid flow shop scheduling problem(RHFSP)with a bottleneck stage is considered,and an elite-class teaching-learning-based optimization(ETLBO)algorithm is proposed to minimize maximum completion time.To produce high-quality solutions,teachers are divided into formal ones and substitute ones,and multiple classes are formed.The teacher phase is composed of teacher competition and teacher teaching.The learner phase is replaced with a reinforcement search of the elite class.Adaptive adjustment on teachers and classes is established based on class quality,which is determined by the number of elite solutions in class.Numerous experimental results demonstrate the effectiveness of new strategies,and ETLBO has a significant advantage in solving the considered RHFSP.

求解无等待Flow shop调度问题的改进蛙跳算法

无等待Flow shop调度一直是研究的热点问题,为减少无等待流水车间调度总完工时间,文章提出了一种结合高斯变异和扰动因子的蛙跳算法。在蛙群更新策略中引入扰动因子,平衡了蛙跳算法搜索的深度,利用高斯变异产生子代新蛙代替随机产生子代新蛙,增强了蛙跳算法的寻优速度;同时引入交叉操作,增加蛙群的多样性,提高蛙群中所有青蛙的局部搜索能力以及全局搜索能力。研究了无等待Flow shop调度算例,将蛙跳算法与遗传算法的求解结果进行了对比,结果验证了该文改进蛙跳算法在解决无等待流水车间调度问题的有效性和可行性。

用QPSO算法求解模糊交货期Flow-shop调度问题

针对模糊交货期Flow-shop调度问题的特点,运用一种收敛速度快、全局性能好、不易陷入局部最优的智能迭代算法-量子粒子群算法,对其进行求解。通过仿真实例对该算法进行了验证,结果表明,在求解模糊交货期的Flow-shop问题时,量子粒子群算法要优于遗传算法和基本粒子群算法。

基于遗传算法的大型Flow-shop生产调度

Flow-shop调度问题具有建模复杂性、计算复杂性、动态多约束、多目标性等特点。近几年,各种演化计算方法逐渐被引入到生产调度中,特别是遗传算法的应用。为此,应用Matlab开发生产调度程序,并利用实际生产数据进行了仿真;通过相关仿真实验,验证了不同交叉算子和变异算子组合获得的最优解存在差异,获得并验证了一种较好的交叉算子和变异算子组合,其仿真调度数据验证了遗传算法用于求解大型流水车间调度的可行性和有效性。

求解Flow-shop调度问题的HSGATS算法研究

通过研究流程企业典型生产加工方式的Flow-shop加工调度问题,分析了求解这一调度问题的各种算法的性能,特别是混合遗传算法中的混合策略,进而提出了一种以启发式搜索算法为前置算法、遗传算法为主体算法、禁忌搜索算法为后置算法的新的混合遗传算法-HSGATS算法,并针对置换Flow-shop调度问题提出了具体的算法设计和实现方法;通过对大量置换Flow--ShopBenchmark问题进行实验求解和其他算法的比较分析,验证了此算法是十分有效的。

混合Flow Shop调度问题的遗传算法求解

该文构造了一种新的遗传启发搜索算法,用于求解混Flow—Shop调度问题,通过分析和实例计算表明,该算法能够有效地适用于大规模加工过程中调度问题的优化计算,在运行时间、适应性和最优率等方面都具有很好的搜索优势。

Flow-Shop系统的鲁棒性研究

使用极大代数模块网络法 ,研究了 Flow- shop离散事件动态系统在没有缓冲器下的无阻塞鲁棒性及最优鲁棒控制 ,提出了系统鲁棒性的 Kharitonov- 1ike判据 ,证明了最优鲁棒控制是一类线性状态反馈 ;还讨论了鲁棒控制系统的周期稳定性和鲁棒极点对摄动参数的敏感性 .

考虑工件准备时间的Semi-Flow-Shop装配调度问题研究

提出一种类似于Flow-Shop调度问题(FSP)但又区别于FSP的Semi-Flow-Shop装配调度问题(SFSP),即在系列产品的装配中,某些产品可以跳过装配工艺中的几道工序而直接进入下道工序。根据实际情况,同时考虑了工件的准备时间及劳动力资源约束。针对该类问题,以最小化生产周期为目标建立数学模型,并设计了一种改进的双层自适应单亲遗传算法,实例证明该算法具有较高的有效性。

双疫苗的免疫遗传算法在求解置换Flow-shop问题中的应用

为提升免疫遗传算法求解置换Flow-shop问题时的寻优速度,提出双疫苗技术。利用NEH算法得到较优排序结果作为前置疫苗,以改善进化初期最佳个体疫苗质量较差的缺陷,提高算法在进化初期的寻优速度;当种群中最佳个体质量更优时,改由该个体作为疫苗进行接种。最后对标准案例进行了测试,结果表明,具有双疫苗技术的算法寻优速度更佳,并能得到更好的作业调度方案。

A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling

A discrete artificial bee colony algorithm is proposed for solving the blocking flow shop scheduling problem with total flow time criterion. Firstly, the solution in the algorithm is represented as job permutation. Secondly, an initialization scheme based on a variant of the NEH (Nawaz-Enscore-Ham) heuristic and a local search is designed to construct the initial population with both quality and diversity. Thirdly, based on the idea of iterated greedy algorithm, some newly designed schemes for employed bee, onlooker bee and scout bee are presented. The performance of the proposed algorithm is tested on the well-known Taillard benchmark set, and the computational results demonstrate the effectiveness of the discrete artificial bee colony algorithm. In addition, the best known solutions of the benchmark set are provided for the blocking flow shop scheduling problem with total flow time criterion.

An effective discrete artificial bee colony algorithm for flow shop scheduling problem with intermediate buffers

An effective discrete artificial bee colony(DABC) algorithm is proposed for the flow shop scheduling problem with intermediate buffers(IBFSP) in order to minimize the maximum completion time(i.e makespan). The effective combination of the insertion and swap operator is applied to producing neighborhood individual at the employed bee phase. The tournament selection is adopted to avoid falling into local optima, while, the optimized insert operator embeds in onlooker bee phase for further searching the neighborhood solution to enhance the local search ability of algorithm. The tournament selection with size 2 is again applied and a better selected solution will be performed destruction and construction of iterated greedy(IG) algorithm, and then the result replaces the worse one. Simulation results show that our algorithm has a better performance compared with the HDDE and CHS which were proposed recently. It provides the better known solutions for the makespan criterion to flow shop scheduling problem with limited buffers for the Car benchmark by Carlier and Rec benchmark by Reeves. The convergence curves show that the algorithm not only has faster convergence speed but also has better convergence value.

Flow shop rescheduling problem under rush orders

In the environment of customization, disturbances such as rush orders and material shortages often occur in the manufacturing system, so rescheduling is necessary for the manufacturing system. The rescheduling methodology should be able to dispose of the disturbance efficiently so as to keep production going smoothly. This aims researching flow shop rescheduling problem (FSRP) necessitated by rush orders. Disjunctive graph is employed to demonstrate the FSRP. For a flow shop processing n jobs, after the original schedule has been made, and z out of n jobs have been processed in the flow shop, x rush orders come, so the original n jobs together with x rush orders should be rescheduled immediately so that the rush orders would be processed in the shortest time and the original jobs could be processed subject to some optimized criteria. The weighted mean flow time of both original jobs and rush orders is used as objective function. The weight for rush orders is much bigger than that of the original jobs, so the rush orders should be processed early in the new schedule. The ant colony optimization (ACO) algorithm used to solve the rescheduling problem has a weakness in that the search may fall into a local optimum. Mutation operation is employed to enhance the ACO performance. Numerical experiments demonstrated that the proposed algorithm has high computation repeatability and efficiency.

Integrated Production and Transportation Scheduling Method in Hybrid Flow Shop

The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies have considered them simultaneously. This paper solves the integrated production and transportation scheduling problem(IPTSP) in hybrid flow shops, which is an extension of the hybrid flow shop scheduling problem(HFSP). In addition to the production scheduling on machines, the transportation scheduling process on automated guided vehicles(AGVs)is considered as another optimization process. In this problem, the transfer tasks of jobs are performed by a certain number of AGVs. To solve it, we make some preparation(including the establishment of task pool, the new solution representation and the new solution evaluation), which can ensure that satisfactory solutions can be found efficiently while appropriately reducing the scale of search space. Then, an effective genetic tabu search algorithm is used to minimize the makespan. Finally, two groups of instances are designed and three types of experiments are conducted to evaluate the performance of the proposed method. The results show that the proposed method is effective to solve the integrated production and transportation scheduling problem.

Anomalies in Special Permutation Flow Shop Scheduling Problems

Recent researches show that there are some anomalies,which are not satisfied with common sense,appearing in some special permutation flow shop scheduling problems(PFSPs).These anomalies can be divided into three different types,such as changing the processing time of some operations,changing the number of total jobs and changing the number of total machines.This paper summarizes these three types of anomalies showing in the special PFSPs and gives some examples to make them better understood.The extended critical path is proposed and the reason why these anomalies happen in special PFSPs is given:anomalies will occur in these special PFSPs when the time of the operations on the reverse critical path changes.After that,the further reason for these anomalies is presented that when any one of these three types of anomalies happens,the original constraint in the special PFSPs is destroyed,which makes the anomalies appear.Finally,the application of these anomalies in production practice is given through examples and also with the possible research directions.The main contribution of this research is analyzing the intial reason why the anomalies appear in special PFSPs and pointing out the application and the possible research directions of all these three types of anomalies.

A novel hybrid estimation of distribution algorithm for solving hybrid flowshop scheduling problem with unrelated parallel machine

The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.

An Enhanced NEH Method in Solving Permutation Flow Shop Problem

This paper proposed an enhanced NEH with full insertion moves to solve the permutation flow shop problem.The characteristics of the original NEH are investigated and analyzed,and it is concluded that the given method would be promising to find better solutions,while the cost would be increased.Fast makespan calculating method and eliminating non-promising permutation policy are introduced to reduce the evaluation effort.The former decreases the time complexity from O(n4m) to O(n3m),which is an acceptable cost for medium and small size instances considering the obtained solution quality.The results from computational experience show that the latter also can eliminate a lot of non-promising solutions.