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.     

多目标柔性作业调度的优化研究

针对以生产周期、生产成本、设备利用率为目标的柔性作业调度问题,基于混合遗传算法提出了一种新的优化求解方法。首先建立了该类问题的调度模型,基于工序编码的染色体决定了工序调度的优先级;利用无量纲的标准化处理方法统一目标量纲;然后,利用层次分析法将多目标问题转化为单目标问题,同时为了保证算法的收敛性,在基本遗传算法框架的基础上集成了禁忌搜索算法,从而延缓或避免了早熟收敛的发生。最后通过实验仿真,证明提出的方法可以有效解决该类多目标柔性作业调度问题。     

A parallel membrane inspired harmony search for optimization problems: A case study based on a flexible job shop scheduling problem

Harmony search is an emerging meta-heuristic optimization algorithm that is inspired by musical improvisation processes, and it can solve various optimization problems. Membrane computing is a distributed and parallel model for solving hard optimization problems. First, we employed some previously proposed approaches to improve standard harmony search by allowing its parameters to be adaptive during the processing steps. Information from the best solutions was used to improve the speed of convergence while preventing premature convergence to a local minimum. Second, we introduced a parallel framework based on membrane computing to improve the harmony search. Our approach utilized the parallel membrane computing model to execute parallelized harmony search efficiently on different cores, where the membrane computing communication characteristics were used to exchange information between the solutions on different cores, thereby increasing the diversity of harmony search and improving the performance of harmony search. Our simulation results showed that the application of the proposed approach to different variants of harmony search yielded better performance than previous approaches. Furthermore, we applied the parallel membrane inspired harmony search to the flexible job shop scheduling problem. Experiments using well-known benchmark instances showed the effectiveness of the algorithm.     

Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm

Most flexible job shop scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines may be unavailable due to maintenances, pre-schedules and so on. In this paper, we study the flexible job shop scheduling problem with availability constraints. The availability constraints are non-fixed in that the completion time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure. We then propose a hybrid genetic algorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints (fJSP-nfa). The genetic algorithm uses an innovative representation method and applies genetic operations in phenotype space in order to enhance the inheritability. We also define two kinds of neighbourhood for the problem based on the concept of critical path. A local search procedure is then integrated under the framework of the genetic algorithm. Representative flexible job shop scheduling benchmark problems and fJSP-nfa problems are solved in order to test the effectiveness and efficiency of the suggested methodology. Received: June 2005 /Accepted: December 2005     

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 hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems

This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and min total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach.     

Parallel hybrid metaheuristics for the flexible job shop problem

A parallel approach to flexible job shop scheduling problem is presented in this paper. We propose two double-level parallel metaheuristic algorithms based on the new method of the neighborhood determination. Algorithms proposed here include two major modules: the machine selection module refer to executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, therefore we call this method meta²heuristics. We carry out a computational experiment using Graphics Processing Units (GPU). It was possible to obtain the new best known solutions for the benchmark instances from the literature.     

A tabu search algorithm for the job shop problem with sequence dependent setup times

This paper addresses the classic job shop scheduling problem where sequence dependent setup times are present. Based on a modified disjunctive graph, we further investigate and generalize structural properties for the problem under study. A tabu search algorithm with a sophisticated neighbourhood structure is then developed. Compared to most studies in this research area, we are interested in moving internal critical operations rather than merely focusing on non-internal ones. Moreover, neighbourhood functions are defined using insertion techniques instead of simple swaps. Test results show that our algorithm outperforms a simulated annealing algorithm which is recently published. We have also conducted experiments considering the efficiency of developed propositions.     

Tardiness minimization in a flexible job shop: A tabu search approach

This paper addresses the problem of scheduling jobs in a flexible job shop with the objective of minimizing total tardiness. The flexible job shop differs from the classical job shop in that each of the operations associated with a job can be processed on any of a set of alternative machines. Two heuristics based on tabu search are developed for this problem: a hierarchical procedure and a multiple start procedure. The procedures use dispatching rules to obtain an initial solution and then search for improved solutions in neighborhoods generated by the critical paths of the jobs in a disjunctive graph representation. Diversification strategies are also implemented and tested. The outcomes of extensive computational results are reported.     

Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion

This study investigates the flexible job shop scheduling problem (FJSP) with new job insertion. FJSP with new job insertion includes two phases: initializing schedules and rescheduling after each new job insertion. Initializing schedules is the standard FJSP problem while rescheduling is an FJSP with different job start time and different machine start time. The time to do rescheduling is the same as the time of new job insertion. Four ensembles of heuristics are proposed for scheduling FJSP with new job insertion. The objectives are to minimize maximum completion time (makespan), to minimize the average of earliness and tardiness (E/T), to minimize maximum machine workload (Mworkload) and total machine workload (Tworkload). Extensive computational experiments are carried out on eight real instances from remanufacturing enterprise. The results and comparisons show the effectiveness of the proposed heuristics for solving FJSP with new job insertion.     

A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem

Tabu search (TS) algorithms are among the most effective approaches for solving the job shop scheduling problem (JSP) which is one of the most difficult NP-complete problems. However, neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of the tabu search for the JSP. In this paper, a new enhanced neighborhood structure is proposed and applied to solving the job shop scheduling problem by TS approach. Using this new neighborhood structure combined with the appropriate move evaluation strategy and parameters, we tested the TS approach on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our approach dominates all others in terms of both solution quality and performance.     

New local diversification techniques for flexible job shop scheduling problem with a multi-agent approach

The Flexible Job Shop problem is among the hardest scheduling problems. It is a generalization of the classical Job Shop problem in that each operation can be processed by a set of resources and has a processing time depending on the resource used. The objective is to assign and to sequence the operations on the resources so that they are processed in the smallest time. In our previous work, we have proposed two Multi-Agent approaches based on the Tabu Search (TS) meta-heuristic. Depending on the location of the optimisation core in the system, we have distinguished between the global optimisation approach where the TS has a global view on the system and the local optimisation approach (FJS MATSLO) where the optimisation is distributed among a collection of agents, each of them has its own local view. In this paper, firstly, we propose new diversification techniques for the second approach in order to get better results and secondly, we propose a new promising approach combining the two latter ones. Experimental results are also presented in this paper in order to evaluate these new techniques.     

A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths

As an extension of the classical job shop scheduling problem, flexible job shop scheduling problem (FJSP) is considered as a challenge in manufacturing systems for its complexity and flexibility. Meta-heuristic algorithms are shown effective in solving FJSP. However, the multiple critical paths issue, which has not been formally discussed in the existing literature, is discovered to be a primary obstacle for further optimization by meta-heuristics. In this paper, a hybrid Jaya algorithm integrated with Tabu search is proposed to solve FJSP for makespan minimization. Two Jaya operators are designed to improve solutions under a two-vector encoding scheme. During the local search phase, three approaches are proposed to deal with multiple critical paths and have been evaluated by experimental study and qualitative analyses. An incremental parameter setting strategy and a makespan estimation method are employed to speed up the searching process. The proposed algorithm is compared with several state-of-the-art algorithms on three well-known FJSP benchmark sets. Extensive experimental results suggest its superiority in both optimality and stability. Additionally, a real world scheduling problem, including six instances with different scales, is applied to further prove its ability in handling large-scale scheduling problems.     

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.     

A tabu search/path relinking algorithm to solve the job shop scheduling problem

We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to generate solutions to the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing features, such as a specific relinking procedure to effectively construct a path linking the initiating solution and the guiding solution, and a reference solution determination mechanism based on two kinds of improvement methods. We evaluate the performance of TS/PR on almost all of the benchmark JSP instances available in the literature. The test results show that TS/PR obtains competitive results compared with state-of-the-art algorithms for JSP in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, TS/PR is able to improve the upper bounds for 49 out of the 205 tested instances and it solves a challenging instance that has remained unsolved for over 20 years.     

Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop

Much of the research on operations scheduling problems has ignored dynamic events in real-world environments where there are complex constraints and a variety of unexpected disruptions. Besides, while most scheduling problems which have been discussed in the literature assume that machines are incessantly available, in most real life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to a scheduled preventive maintenance where the periods of unavailability are determined in advance (deterministic unavailability). This paper describes how we can integrate simulation into genetic algorithm to the dynamic scheduling of a flexible job shop with machines that suffer stochastic breakdowns. The objectives are the minimization of two criteria, expected makespan and expected mean tardiness. An overview of the flexible job shops and scheduling under the stochastic unavailability of machines are presented. Subsequently, the details of integrating simulation into genetic algorithm are described and implemented. Consequently, problems of various sizes are used to test the performance of the proposed algorithm. The results obtained reveal that the relative performance of the algorithm for both abovementioned objectives can be affected by changing the levels of the breakdown parameters.     

A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times

In this paper, we propose a model for Flexible Job Shop Scheduling Problem (FJSSP) with transportation constraints and bounded processing times. This is a NP hard problem. Objectives are to minimize the makespan and the storage of solutions. A genetic algorithm with tabu search procedure is proposed to solve both assignment of resources and sequencing problems on each resource. In order to evaluate the proposed algorithm's efficiency, five types of instances are tested. Three of them consider sequencing problems with or without assignment of processing or/and transport resources. The fourth and fifth ones introduce bounded processing times which mainly characterize Surface Treatment Facilities (STFs). Computational results show that our model and method are efficient for solving both assignment and scheduling problems in various kinds of systems.     

基于自适应参数与混沌搜索的PSO算法求解柔性作业车间调度问题

针对传统粒子群优化(PSO)算法在求解柔性作业车间调度问题中的不足,提出了基于自适应参数与混沌搜索的粒子群优化算法。对粒子群算法中的惯性系数等参数采用基于迭代搜索而自适应调整的方式,使粒子在初期以较大惯性进行大范围搜索,后期逐渐减小惯性而转入精细搜索。这种方法改变了传统粒子群算法在求解过程中的盲目随机与求解精度不高的问题;同时,通过在局部搜索过程中引入混沌技术,扩大对最优解的寻找范围,以此避免算法陷入局部最优,有效提高算法的全局寻优能力。实验结果表明,基于自适应参数与混沌搜索的粒子群优化算法在求解柔性作业车间调度问题(FJSP)时能够获得更优粒子适应度平均值及更好的优化目标。所提算法对求解柔性作业车间调度问题可行,有效。     

A fast hybrid tabu search algorithm for the no-wait job shop problem

This paper describes a hybrid tabu search algorithm dedicated to a job shop problem with a no-wait constraint with a makespan criterion. The proposed here algorithm complexity is that the superior algorithm based on the tabu search technique selects parameters controlling the work of a certain constructional algorithm. This approach limits the checked solutions only to a group of solutions being able to be generated by the structural algorithm in question. It bears serious consequences both positive, for example it limits the research scope for a small fraction of relatively extremely well quality of acceptable solutions, and negative that is the lack of possibility of finding the optimal solution. In this paper numerical researches of the proposed algorithm are conducted as well as a comparative analysis with reference to the literature algorithms of the algorithm in question is made.