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.

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.

Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage

This paper considers a scheduling problem in two-stage hybrid flow shop, where the first stage consists of two machines formed an open shop and the other stage has only one machine. The objective is to minimize the makespan, i.e., the maximum completion time of all jobs. We first show the problem is NP-hard in the strong sense, then we present two heuristics to solve the problem. Computational experiments show that the combined algorithm of the two heuristics performs well on randomly generated problem instances.

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.

Differential evolution algorithm for hybrid flow-shop scheduling problems

Aiming at the hybrid flow-shop （HFS） scheduling that is a complex NP-hard combinatorial problem with wide engineering background, an effective algorithm based on differential evolution （DE） is proposed. By using a special encoding scheme and combining DE based evolutionary search and local search, the exploration and exploitation abilities are enhanced and well balanced for solving the HFS problems. Simulation results based on some typical problems and comparisons with some existing genetic algorithms demonstrate the proposed algorithm is effective, efficient and robust for solving the HFS problems.

Local Search Algorithm with Hybrid Neighborhood and Its Application to Job Shop Scheduling Problem

A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson (ie., FT6 and FT20)is made. The experiment results show the better optimal performance of the proposed algorithm.

An Improved Hyperplane Assisted Multiobjective Optimization for Distributed Hybrid Flow Shop Scheduling Problem in Glass Manufacturing Systems

To solve the distributed hybrid flow shop scheduling problem(DHFS)in raw glass manufacturing systems,we investigated an improved hyperplane assisted evolutionary algorithm(IhpaEA).Two objectives are simultaneously considered,namely,the maximum completion time and the total energy consumptions.Firstly,each solution is encoded by a three-dimensional vector,i.e.,factory assignment,scheduling,and machine assignment.Subsequently,an efficient initialization strategy embeds two heuristics are developed,which can increase the diversity of the population.Then,to improve the global search abilities,a Pareto-based crossover operator is designed to take more advantage of non-dominated solutions.Furthermore,a local search heuristic based on three parts encoding is embedded to enhance the searching performance.To enhance the local search abilities,the cooperation of the search operator is designed to obtain better non-dominated solutions.Finally,the experimental results demonstrate that the proposed algorithm is more efficient than the other three state-of-the-art algorithms.The results show that the Pareto optimal solution set obtained by the improved algorithm is superior to that of the traditional multiobjective algorithm in terms of diversity and convergence of the solution.

Hybrid Flow Shop with Setup Times Scheduling Problem

The two-stage hybridflow shop problem under setup times is addressed in this paper.This problem is NP-Hard.on the other hand,the studied problem is modeling different real-life applications especially in manufacturing and high performance-computing.Tackling this kind of problem requires the development of adapted algorithms.In this context,a metaheuristic using the genetic algorithm and three heuristics are proposed in this paper.These approximate solutions are using the optimal solution of the parallel machines under release and delivery times.Indeed,these solutions are iterative procedures focusing each time on a particular stage where a parallel machines problem is called to be solved.The general solution is then a concatenation of all the solutions in each stage.In addition,three lower bounds based on the relaxation method are provided.These lower bounds present a means to evaluate the efficiency of the developed algorithms throughout the measurement of the relative gap.An experimental result is discussed to evaluate the performance of the developed algorithms.In total,8960 instances are implemented and tested to show the results given by the proposed lower bounds and heuristics.Several indicators are given to compare between algorithms.The results illustrated in this paper show the performance of the developed algorithms in terms of gap and running time.

基于遗传算法的混合Flow-shop调度方法

混合Flow-shop调度问题 (Hybrid flow-shop scheduling problem, HFSP),是一般Flow-shop调度问题的推广,由于在某些工序上存在并行机器,所以比一般的Flow-shop调度问题更复杂。本文提出了遗传算法求解混合Flow-shop调度问题的方法,给出了一种新的编码方法,设计了相应的交叉和变异操作算子,能够保证个体的合法性,同时又具有遗传算法本身所要求的随机性。最后给出了某汽车发动机厂金加工车间的生产调度实例,表明了此算法的有效性。

基于混合粒子群算法的多目标柔性Job-Shop调度方法

针对经典Job-Shop调度问题的局限性,提出了以时间、成本、质量三者综合为优化目标,具有柔性Job-Shop车间调度的优化模型。给出了优化目标的计算方法,并设计了混合粒子群算法,给出了使用此算法求解模型的具体实现过程。模型采用工序能力指数对质量目标进行量化,并采用综合评判线性加权模型解决柔性Job-Shop算法的权重选择问题,使决策者能够根据实际情况选择优化目标的偏好解。通过一个车间调度问题的实例验证了此调度模型和算法的有效性。

一种求解Job Shop调度问题的混合粒子群优化算法

目的解决单一粒子群算法求解Job Shop调度问题存在的不足,提高这类问题的求解质量.方法采用粒子群算法进行全局搜索,将禁忌搜索算法用于并行局部搜索,禁忌搜索在找到改进解的邻域时采用动态记忆的方式.结果在较短时间内,找到了LA21,LA24等典型benchmarks问题的最优解,十次求解的平均值的平均相对误差百分比比并行遗传算法和禁忌搜索算法分别小了2.94%和0.56%.结论提出一种混合粒子群算法,增强了粒子群算法的局部搜索能力,说明该混合粒子群优化算法是有效的.

基于准时制的零等待混合 Flow Shop 调度问题

讨论了具有零等待混合ＦｌｏｗＳｈｏｐ调度问题，其目标是最小化提前／拖期总成本．这是一个ＮＰ难题．给出了问题的数学模型，同时将启发式算法和求解线性规划相结合，提出了这一调度模型的求解方法．最后给出了实验结果和结论．

求解Job Shop调度问题的粒子群算法研究

为解决单一粒子群算法求解Job Shop调度问题存在的不足,提出一种基于交换序的混合粒子群算法,提高了这类问题的求解质量。在混合粒子群算法中,采用粒子群算法进行大范围全局搜索。根据Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种方法的禁忌搜索算法作为局部搜索算法,增强了粒子群算法的搜索能力。采用混合粒子群算法对13个难解的benchmark问题进行求解,在较短的时间内,得到的最优解和10次求解的平均值优于并行遗传算法和粒子群算法。由此说明本文所提出的混合粒子群算法是有效的。

神经网络和启发式算法混合策略解Job-shop调度问题

提出一种有效的自适应神经网络和启发式算法混合策略来求解Ｊｏｂｓｈｏｐ调度问题．自适应神经网络具有在网络运行过程中神经元的偏置和连接权值自适应取值的特性，被用来求得调度问题的可行解，而启发式算法被分别用来加速神经网络的运行和保证神经网络收敛到可行解、获得确定排序下最优解和提高可行解的质量．

基于自适应遗传算法混合Flow-shop的调度与仿真

通过对柔性制造系统中混合流水车间生产调度问题的分析和研究,开发了基于遗传算法的生产调度方法,调度目标为最小化工件的最大完工时间。采用了一套新的染色体编码方法以保证个体的合法性与计算的方便性,设计了相应的交叉和变异操作算子,并生成最优的排序计划。仿真结果表明,改进后的顺序自适应交叉遗传算法更能有效地解决混合流水车间调度问题,并采用VB软件编程实现了调度过程的动态仿真。

计及机器调整和物料运送时间的Job-Shop调度算法

对考虑机器调整时间和物料运送时间的Job-Shop调度问题进行了研究。优化计算时考虑了物料运送时间的作用及其对车间调度的影响,并给出了其求解方法;利用GA、SA与PSO相结合的混合PSO算法解决了Job-Shop调度问题。仿真实例模拟实际工况,对工件的运送、加工和机器调整时间及其相互间的影响进行了分析和计算,并与传统的忽略机器调整时间、物料运送时间以及直接计入工件加工时间的调度方案进行了对比,结果表明提出的方法可行,更加符合实际生产工况。

一种混合粒子群算法及其在Job Shop问题中的应用

粒子群算法是一种新颖的演化计算技术,具有思想简单、容易实现的优点,被广泛应用于连续空间的优化。结合遗传算法的思想提出一种新的进化方式并用于Job Shop离散空间优化,进一步结合粒子群算法的群体多样性和禁忌搜索算法的集中搜索性提出一种粒子群算法和禁忌搜索算法的混合策略。用Job Shop问题作为测试基准,仿真试验显示混合粒子群算法是可行和有效的。

多阶段混合Flow Shop调度问题及其遗传求解算法

针对多阶段混合Ｆｌｏｗ Ｓｈｏｐ 调度问题的一般结构和不同的调度目标函数，提出混合整数规划模型，并基于问题的结构特点设计了遗传求解算法。计算实验结果表明。

一类Job-shop多目标优化调度方法

提出了一类Job-shop多目标优化调度方法。构建了一个以工件平均流程时间最短、全部工件完工时间最短的Job-shop优化调度模型,并针对模型提出了一种分阶段混合变异的禁忌搜索算法。为增强算法收敛性,利用"逆序变异"和"基因段交换变异"找到了较好的初解,在此基础上利用"基因交换变异"继续搜索近优解。以10个算例验证了提出的Job-shop多目标优化调度方法的正确性和有效性。