Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem

The multi-objective flexible job shop scheduling problem is solved using a novel path-relinking algorithm based on the state-of-the-art Tabu search algorithm with back-jump tracking. A routing solution is identified by problem-specific neighborhood search, and is then further refined by the Tabu search algorithm with back-jump tracking for a sequencing decision. The resultant solution is used to maintain the medium-term memory where the best solutions are stored. A path-relinking heuristics is designed to generate diverse solutions in the most promising areas. An improved version of the algorithm is then developed by incorporating an effective dimension-oriented intensification search to find solutions that are located near extreme solutions. The proposed algorithms are tested on benchmark instances and its experimental performance is compared with that of algorithms in the literature. Comparison results show that the proposed algorithms are competitive in terms of its computation performance and solution quality.     

Modelling and scheduling multi-objective flow shop problems with interfering jobs

This paper studies multi-objective flow shop scheduling problems with interfering jobs. That is, there are two sets of jobs and each of which has its own objective. Some jobs are scheduled so as to minimize makespan while the others are to minimize total tardiness. In this case, the problem was mathematically modeled by a mixed integer linear program. Then, a novel biogeography-based optimization was developed to solve the problem. To evaluate the algorithm, its performance was compared with three well-known algorithms in the literature. The results of the present study show that the proposed algorithm outperforms the other tested algorithms.     

A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: Weighted mean completion time and weighted mean tardiness

This paper investigates a novel multi-objective model for a no-wait flow shop scheduling problem that minimizes both the weighted mean completion time and weighted mean tardiness . Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new hybrid multi-objective algorithm based on the features of a biological immune system (IS) and bacterial optimization (BO) to find Pareto optimal solutions for the given problem. To validate the performance of the proposed hybrid multi-objective immune algorithm (HMOIA) in terms of solution quality and diversity level, various test problems are examined. Further, the efficiency of the proposed algorithm, based on various metrics, is compared against five prominent multi-objective evolutionary algorithms: PS-NC GA, NSGA-II, SPEA-II, MOIA, and MISA. Our computational results suggest that our proposed HMOIA outperforms the five foregoing algorithms, especially for large-sized problems.     

A Pareto archive particle swarm optimization for multi-objective job shop scheduling

In this paper, we present a particle swarm optimization for multi-objective job shop scheduling problem. The objective is to simultaneously minimize makespan and total tardiness of jobs. By constructing the corresponding relation between real vector and the chromosome obtained by using priority rule-based representation method, job shop scheduling is converted into a continuous optimization problem. We then design a Pareto archive particle swarm optimization, in which the global best position selection is combined with the crowding measure-based archive maintenance. The proposed algorithm is evaluated on a set of benchmark problems and the computational results show that the proposed particle swarm optimization is capable of producing a number of high-quality Pareto optimal scheduling plans.     

An effective asexual genetic algorithm for solving the job shop scheduling problem

By using the notion of elite pool, this paper presents an effective asexual genetic algorithm for solving the job shop scheduling problem. Based on mutation operations, the algorithm selectively picks the solution with the highest quality from the pool and after its modification, it can replace the solution with the lowest quality with such a modified solution. The elite pool is initially filled with a number of non-delay schedules, and then, in each iteration, the best solution of the elite pool is removed and mutated in a biased fashion through running a limited tabu search procedure. A decision strategy which balances exploitation versus exploration determines (i) whether any intermediate solution along the run of tabu search should join the elite pool, and (ii) whether upon joining a new solution to the pool, the worst solution should leave the pool. The genetic algorithm procedure is repeated until either a time limit is reached or the elite pool becomes empty. The results of extensive computational experiments on the benchmark instances indicate that the success of the procedure significantly depends on the employed mechanism of updating the elite pool. In these experiments, the optimal value of the well-known 10 × 10 instance, ft10, is obtained in 0.06 s. Moreover, for larger problems, solutions with the precision of less than one percent from the best known solutions are achieved within several seconds.     

多机并行作业车间调度的混合粒子群算法

本文通过对多目标多机作业车间调度的研究提出了一个改进的结合启发式规则的粒子群算法,采用了依机器和工件排序的编码规则,两段式的表达形式,带启发式规则的调整,并结合聚类分析思想的保留策略,对此类问题提出了一个新的解决方法,并在文中通过一个仿真案例进行求解。     

猫群优化算法求解柔性作业车间调度问题

根据柔性作业车间的生产特点,对基本猫群优化算法进行设计和改进,提出了一种改进型猫群优化算法（Improved Cat Swarm Optimization,ICSO）,用于优化车间内工件的最大完工时间。算法给出了两段式个体位置编码方式和基于启发式算法的种群初始化策略;采用自适应行为模式选择方法,使其能够有效协调算法全局和局部搜索;提出了基于多样化搜寻算子的搜寻模式,增强算法的全局搜索能力;提出了基于莱维飞行的跟踪模式,增强算法的局部搜索能力。此外,算法中还引入了跳跃机制,使算法性能能够得到进一步的改善。实验数据表明ICSO算法在求解FJSP问题方面具有一定的有效性。     

An intelligent water drops-based workflow scheduling for IaaS cloud

Cloud computing is an emerging technology in a distributed environment with a collection of large-scale heterogeneous systems. One of the challenging issues in the cloud data center is to select the minimum number of virtual machine (VM) instances to execute the tasks of a workflow within a time limit. The objectives of such a strategy are to minimize the total execution time of a workflow and improve resource utilization. However, the existing algorithms do not guarantee to achieve high resource utilization although they have abilities to achieve high execution efficiency. The higher resource utilization depends on the reusability of VM instances. In this work, we propose a new intelligent water drops based workflow scheduling algorithm for Infrastructure-as-a-Service (IaaS) cloud. The objectives of the proposed algorithm are to achieve higher resource utilization and minimize the makespan within the given deadline and budget constraints. The first contribution of the algorithm is to find multiple partial critical paths (PCPs) of a workflow which helps in finding suitable VM instances. The second contribution is a scheduling strategy for PCP-VM assignment for assigning the VM instances. The proposed algorithm is evaluated through various simulation runs using synthetic datasets and various performance metrics. Through comparison, we show the superior performance of the proposed algorithm over the existing ones.     

基于新型帝国竞争算法的高维多目标柔性作业车间调度

针对高维多目标柔性作业车间调度问题(MaOFJSP),提出了一种新型帝国竞争算法(ICA)以同时最小化最大完成时间、最大拖期、最大机器负荷和总能耗,该算法采用新方法构建初始帝国使得大多数殖民国家分配数量相近的殖民地,引入殖民国家的同化,并应用新的革命策略和帝国竞争方法以获得高质量解.最后通过大量实验测试ICA新策略对其性能的影响并将ICA与其他算法对比,实验结果表明新型ICA在求解MaOFJSP方面具有较强的优势.     

An efficient search method for multi-objective flexible job shop scheduling problems

Flexible job shop scheduling is very important in both fields of production management and combinatorial optimization. Owing to the high computational complexity, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches. Motivated by some empirical knowledge, we propose an efficient search method for the multi-objective flexible job shop scheduling problems in this paper. Through the work presented in this work, we hope to move a step closer to the ultimate vision of an automated system for generating optimal or near-optimal production schedules. The final experimental results have shown that the proposed algorithm is a feasible and effective approach for the multi-objective flexible job shop scheduling problems.     

An efficient memetic algorithm for solving the job shop scheduling problem

The job shop scheduling problem (JSP) is well known as one of the most complicated combinatorial optimization problems, and it is a NP-hard problem. Memetic algorithm (MA) which combines the global search and local search is a hybrid evolutionary algorithm. In this paper, an efficient MA with a novel local search is proposed to solve the JSP. Within the local search, a systematic change of the neighborhood is carried out to avoid trapping into local optimal. And two neighborhood structures are designed by exchanging and inserting based on the critical path. The objective of minimizing makespan is considered while satisfying a number of hard constraints. The computational results obtained in experiments demonstrate that the efficiency of the proposed MA is significantly superior to the other reported approaches in the literature.     

An improved particle swarm optimization with decline disturbance index (DDPSO) for multi-objective job-shop scheduling problem

As same with many evolutional algorithms, performance of simple PSO depends on its parameters, and it often suffers the problem of being trapped in local optima so as to cause premature convergence. In this paper, an improved particle swarm optimization with decline disturbance index (DDPSO), is proposed to improve the ability of particles to explore the global and local optimization solutions, and to reduce the probability of being trapped into the local optima. The correctness of the modification, which incorporated a decline disturbance index, was proved. The key question why the proposed method can reduce the probability of being trapped in local optima was answered. The modification improves the ability of particles to explore the global and local optimization solutions, and reduces the probability of being trapped into the local optima. Theoretical analysis, which is based on stochastic processes, proves that the trajectory of particle is a Markov processes and DDPSO algorithm converges to the global optimal solution with mean square merit. After the exploration based on DDPSO, neighborhood search strategy is used in a local search and an adaptive meta-Lamarckian strategy is employed to dynamically decide which neighborhood should be selected to stress exploitation in each generation. The multi-objective combination problems with DDPSO for finding the pareto front was presented under certain performance index. Simulation results and comparisons with typical algorithms show the effectiveness and robustness of the proposed DDPSO.     

超启发式遗传算法求解模糊柔性作业车间调度

本文提出一种混合超启发式遗传算法(HHGA),用于求解一类采用三角模糊数表示工件加工时间的模糊柔性作业车间调度问题(FFJSP),优化目标为最小化最大模糊完工时间(即makespan).首先,详细分析现有三角模糊数排序准则性质,并充分考虑取大操作的近似误差和模糊度,设计一种更为准确的三角模糊数排序准则,可合理计算FFJSP和其他各类调度问题解的目标函数值.其次,为实现对FFJSP解空间不同区域的有效搜索, HHGA将求解过程分为两层,高层利用带自适应变异算子的遗传算法对6种特定操作(即6种有效邻域操作)的排列进行优化;低层将高层所得的每种排列作为一种启发式算法,用于对低层相应个体进行操作来执行紧凑的变邻域局部搜索并生成新个体,同时加入模拟退火机制来避免搜索陷入局部极小.最后,仿真实验和算法比较验证了所提排序准则和HHGA的有效性.     

A nature inspired intelligent water drops evolutionary algorithm for parallel processor scheduling with rejection

Scheduling has become a popular area for artificial intelligence and expert system researchers during last decade. In this paper, a new metaheuristic algorithm entitled intelligent water drops (IWD) is adapted for solving a generalized kind of order scheduling problem where rejection of received orders is allowed with a penalty cost. At the beginning of production period, a set of orders are received by manufacturer. Due to capacity limit, the manufacturer can only process a subset of orders and has to decide to reject some of undesirable orders. The accepted orders are proceed to be scheduled by a set of identical parallel processors in shop floor. The objective is to select the best set of orders with high contribution in manufacturer's benefit and then find the appropriate schedule of accepted orders minimizing the number of tardy orders. To effectively solve the suggested problem, the Lexicographic utility function is customized to address different objectives and then an IWD algorithm, which is based on the process of the natural rivers and the interactions among water drops in a river, is devised. To further enhance the performance of basic IWD, an Iterated Local Search (ILS) heuristic is also incorporated into the main algorithm. To demonstrate the applicability of suggested problem and also show the effectiveness of enhanced IWD with ILS, a real-world application in commercial printing industry is presented and the performance of algorithm is compared with traditional algorithms like GA, DE and ACO.     

An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers

This paper proposes an effective hybrid algorithm based on differential evolution (DE), namely HDE, to solve multi-objective permutation flow shop scheduling problem (MPFSSP) with limited buffers between consecutive machines, which is a typical NP-hard combinatorial optimization problem with strong engineering background. Firstly, to make DE suitable for solving scheduling problems, a largest-order-value (LOV) rule is presented to convert the continuous values of individuals in DE to job permutations. Secondly, after the DE-based exploration, an efficient local search, which is designed based on the landscape of MPFSSP with limited buffers, is applied to emphasize exploitation. Thus, not only does the HDE apply the parallel evolution mechanism of DE to perform effective exploration (global search) in the whole solution space, but it also adopts problem-dependent local search to perform thorough exploitation (local search) in the promising sub-regions. In addition, the concept of Pareto dominance is used to handle the updating of solutions in sense of multi-objective optimization. Moreover, the convergence property of HDE is analyzed by using the theory of finite Markov chain. Finally, simulations and comparisons based on benchmarks demonstrate the effectiveness and efficiency of the proposed HDE.     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

带负载均衡的混合算法求解分布式异构作业车间调度问题

针对以最小化最大完工时间为目标的分布式异构作业车间调度问题(DHJSP), 本文提出了一种新的混合遗传禁忌搜索算法. 首先, 综合考虑工厂的工件总负载与最大机器负载, 提出了一种新的工厂负载表达方式. 其次, 针对DHJSP总工序数不定的特性, 提出以最小化最大工厂负载为目标快速确定初始工件分配方案, 并验证了方法的高效性. 然后, 新设计了两种考虑负载均衡的单工件转移邻域结构, 根据工序调度的结果对工件分配方案进行局部搜索. 最后, 因DHJSP缺少标准算例和相关算法, 在分布式同构作业车间调度问题(DJSP)上与现有算法进行对比, 所提算法在TA算例的480个问题上更新了420个问题的最优解, 其余60个问题取得了同等最优解. 在随机生成的3个不同规模的异构算例中, 所提算法也均取得了较好解, 验证了所提方法的优越性.     

基于强化学习的智能车间调度策略研究综述

智能制造是我国制造业发展的必然趋势,而智能车间调度是制造业升级和深化“两化融合”的关键技术。主要研究强化学习算法在车间调度问题中的应用,为后续的研究奠定基础。其中车间调度主要包括静态调度和动态调度;强化学习算法主要包括基于值函数和AC（Actor-Critic）网络。首先,从总体上阐述了强化学习方法在作业车间调度和流水车间调度这两大问题上的研究现状;其次,对车间调度问题的数学模型以及强化学习算法中最关键的马尔可夫模型建立规则进行分类讨论;最后,根据研究现状和当前工业数字化转型需求,对智能车间调度技术的未来研究方向进行了展望。     

An integrated search heuristic for large-scale flexible job shop scheduling problems

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop scheduling problem (JSP), where each operation is allowed to be processed by any machine from a given set, rather than one specified machine. In this paper, two algorithm modules, namely hybrid harmony search (HHS) and large neighborhood search (LNS), are developed for the FJSP with makespan criterion. The HHS is an evolutionary-based algorithm with the memetic paradigm, while the LNS is typical of constraint-based approaches. To form a stronger search mechanism, an integrated search heuristic, denoted as HHS/LNS, is proposed for the FJSP based on the two algorithms, which starts with the HHS, and then the solution is further improved by the LNS. Computational simulations and comparisons demonstrate that the proposed HHS/LNS shows competitive performance with state-of-the-art algorithms on large-scale FJSP problems, and some new upper bounds among the unsolved benchmark instances have even been found.     

A very fast TS/SA algorithm for the job shop scheduling problem

The job shop scheduling problem (JSP) is one of the most notoriously intractable NP-complete optimization problems. Over the last 10–15 years, tabu search (TS) has emerged as an effective algorithmic approach for the JSP. However, the quality of solutions found by tabu search approach depends on the initial solution. To overcome this problem and provide a robust and efficient methodology for the JSP, the heuristics search approach combining simulated annealing (SA) and TS strategy is developed. The main principle of this approach is that SA is used to find the elite solutions inside big valley (BV) so that TS can re-intensify search from the promising solutions. This hybrid algorithm is tested on the standard benchmark sets and compared with the other approaches. The computational results show that the proposed algorithm could obtain the high-quality solutions within reasonable computing times. For example, 17 new upper bounds among the unsolved problems are found in a short time.