Discrepancy search for the flexible job shop scheduling problem

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop problem in which each operation must be processed on a given machine chosen among a finite subset of candidate machines. The aim is to find an allocation for each operation and to define the sequence of operations on each machine, so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. We also present various neighborhood structures related to assignment and sequencing problems. We report the results of extensive computational experiments carried out on well-known benchmarks for flexible job shop scheduling. The results demonstrate that the proposed approach outperforms the best-known algorithms for the FJSP on some types of benchmarks and remains comparable with them on other ones.     

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 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.     

Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives

Flexible job-shop scheduling problem (FJSP) is a practically useful extension of the classical job shop scheduling problem. This paper proposes an effective discrete harmony search (DHS) algorithm to solve FJSP. The objectives are the weighted combination of two minimization criteria namely, the maximum of the completion time (Makespan) and the mean of earliness and tardiness. Firstly, we develop a new method for the initial machine assignment task. Some existing heuristics are also employed for initializing the harmony memory with discrete machine permutation for machine assignment and job permutation for operation sequencing. Secondly, we develop a new rule for the improvisation to produce a new harmony for FJSP incorporating machine assignment and operation sequencing. Thirdly, several local search methods are embedded to enhance the algorithm’s local exploitation ability. Finally, extensive computational experiments are carried out using well-known benchmark instances. Computational results and comparisons show the efficiency and effectiveness of the proposed DHS algorithm for solving the FJSP with weighted combination of two objectives.     

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.     

求解柔性作业调度问题的协同进化粒子群算法

柔性作业车间调度问题是典型的NP难题。柔性作业车间调度问题涉及到设备分配和作业分配两个问题,并且两问题之间具有较强的耦合性,提出了基于协同进化的粒子群算法。该算法将设备选择和工件调度分别作为两个寻优变量,利用PSO算法分别进行寻优,根据两个变量的内容进行互相评价。实验表明该算法对FJSP问题的有效性。     

A new immune multi-agent system for the flexible job shop scheduling problem

Scheduling for the flexible job shop is very important and challenging in manufacturing field. Multi-agent-based approaches have been used to solve the flexible job shop scheduling problem (FJSP), in order to reduce complexity and cost, increase flexibility, and enhance robustness. However, the quality of solution obtained by the multi-agent approach is always worse than the centralized meta-heuristic algorithms. The immune system is a distributed and complicated information processing system, which can protect body from foreign antigens by immune responses. In this paper, we analyze the similarities between the FJSP and humoral immunity, which is one of the immune responses. Based on the similarities, we develop a new immune multi-agent scheduling system (NIMASS) to solve the FJSP with the objective of minimizing the maximal completion time (makespan). In order to acquire the higher-quality solution of the FJSP, we simulate humoral immunity to establish the architecture of NIMASS and the negotiation strategies of NIMASS, which are proposed for negotiation among agents. NIMASS was tested on different benchmark instances of the FJSP. In comparison with the multi-agent approaches and the centralized heuristic algorithms, the computational results indicate that NIMASS can effectively improve the quality of solution in very short time. And the computational time of NIMASS is superior to that of the centralized meta-heuristic algorithms, especially for the complex FJSPs. These results indicate that NIMASS can be very useful in applications that deal with real-time FJSPs.     

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.     

A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines,setup times,and dual criteria

This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0–1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms.     

Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem

This paper investigates integrated flexible job shop problem (FJSP) with preventive maintenance (PM) activities under the multi-objective optimization approaches. Finding compromise solutions between the production objectives and maintenance ones is under consideration. In order to carry out the maintenance activities, reliability models are employed. This paper attempts to simultaneously optimize two objectives: the minimization of the makespan for the production part and the minimization of the system unavailability for the maintenance part. For doing it so, two decisions are taken at the same time: finding the appropriate assignment of n jobs on m machines in order to minimize the makespan and deciding when to execute the PM activities in order to minimize the system unavailability. Both the maintenance activity numbers and maintenance intervals are not fixed in advance. Four multi-objective optimization methods are compared to find the Pareto-optimal front in the flexible job-shop problem case. Promising the obtained results, a benchmark with a large number of test instances (more than 4800) and meticulous care is employed.     

Flexible job shop scheduling using hybrid differential evolution algorithms

This paper proposes hybrid differential evolution (HDE) algorithms for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize the makespan. Firstly, a novel conversion mechanism is developed to make the differential evolution (DE) algorithm that works on the continuous domain adaptive to explore the problem space of the discrete FJSP. Secondly, a local search algorithm based on the critical path is embedded in the DE framework to balance the exploration and exploitation by enhancing the local searching ability. In addition, in the local search phase, the speed-up method to find an acceptable schedule within the neighborhood structure is presented to improve the efficiency of whole algorithms. Extensive computational results and comparisons show that the proposed algorithms are very competitive with the state of the art, some new best known solutions for well known benchmark instances have even been found.     

Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling

Fuzzy flexible job shop scheduling problem (FfJSP) is the combination of fuzzy scheduling and flexible scheduling in job shop environment, which is seldom investigated for its high complexity. We developed an effective co-evolutionary genetic algorithm (CGA) for the minimization of fuzzy makespan. In CGA, the chromosome of a novel representation consists of ordered operation list and machine assignment string, a new crossover operator and a modified tournament selection are proposed, and the population of job sequencing and the population of machine assignment independently evolve and cooperate for converging to the best solutions of the problem. CGA is finally applied and compared with other algorithms. Computational results show that CGA outperforms those algorithms compared.     

Flexible job-shop scheduling with parallel variable neighborhood search algorithm

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. FJSP is NP-hard and mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines. This paper proposes a parallel variable neighborhood search (PVNS) algorithm that solves the FJSP to minimize makespan time. Parallelization in this algorithm is based on the application of multiple independent searches increasing the exploration in the search space. The proposed PVNS uses various neighborhood structures which carry the responsibility of making changes in assignment and sequencing of operations for generating neighboring solutions. The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the FJSP.     

Heuristics for hybrid flow shops with controllable processing times and assignable due dates

This paper considers a generalization of the permutation flow shop problem that combines the scheduling function with the planning stage. In this problem, each work center consists of parallel identical machines. Each job has a different release date and consists of ordered operations that have to be processed on machines from different machine centers in the same order. In addition, the processing times of the operations on some machines may vary between a minimum and a maximum value depending on the use of a continuously divisible resource. We consider a nonregular optimization criterion based on due dates which are not a priori given but can be fixed by a decision-maker. A due date assignment cost is included into the objective function. For this type of problems, we generalize well-known approaches for the heuristic solution of classical problems and propose constructive algorithms based on job insertion techniques and iterative algorithms based on local search. For the latter, we deal with the design of appropriate neighborhoods to find better quality solution. Computational results for problems with up to 20 jobs and 10 machine centers are given.Scope and purposeTraditional research to solve multi-stage scheduling problems has focused on regular measures of performance based on a single criterion and assumes that several decisions related to due dates and processing times have already been made. However, in many industrial scheduling practices, managers develop schedules based on multicriteria and have to decide the due dates and processing times as part of the scheduling activities. Further, in practical scheduling situations, there are multiple machines at each stage and the objective function often reflects the total cost of processing, earliness and tardiness. Such scheduling problems require significantly more effort in finding acceptable solutions and hence have not received much attention in the literature. For this reason, this paper considers one such hybrid flow shop scheduling problem involving nonregular measures of performance, controllable processing times, and assignable due dates. We combine and generalize the existing approaches for the classical flow shop problem to the problem under consideration. Computational experiments are used to evaluate the utility of the proposed algorithms for the generalized scheduling problems. Brah and Hunsucker (European Journal of Operational Research 1991;51:88–99) and Nowicki and Smutnicki (European Journal of Operational Research 1998;106:226–253) describe branch and bound and tabu search algorithms for the approach used in the development of heuristic algorithms can also be adapted to several other complex practical scheduling problems.     

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     

A computer simulation model for job shop scheduling problems minimizing makespan

One of the basic and significant problems, that a shop or a factory manager is encountered, is a suitable scheduling and sequencing of jobs on machines. One type of scheduling problem is job shop scheduling. There are different machines in a shop of which a job may require some or all these machines in some specific sequence. For solving this problem, the objective may be to minimize the makespan. After optimizing the makespan, the jobs sequencing must be carried out for each machine. The above problem can be solved by a number of different methods such as branch and bound, cutting plane, heuristic methods, etc. In recent years, researches have used genetic algorithms, simulated annealing, and machine learning methods for solving such problems. In this paper, a simulation model is presented to work out job shop scheduling problems with the objective of minimizing makespan. The model has been coded by Visual SLAM which is a special simulation language. The structure of this language is based on the network modeling. After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented and compared with other results reported in the literature. Finally, the model output is analyzed.     

A Pareto-based two-stage evolutionary algorithm for flexible job shop scheduling problem with worker cooperation flexibility

The previous studies on the flexible job shop scheduling problems (FJSP) with machine flexibility and worker flexibility normally assume that each machine is operated by one worker at any time. However, it is not accurate in many cases because many workers may be required for machines in processing complex operations. Hence, this paper studies a universal version, i.e., FJSP with worker cooperation flexibility (FJSPWC), which defines that each machine can be used only if their required workers are prepared. A mixed-integer linear programming model tuned by CPLEX is established for the problem aiming to collaboratively minimize the makespan, maximum workload of machines and maximum workload of workers. To solve the problem efficiently, a Pareto-based two-stage evolutionary algorithm (PTEA) is proposed. In the PTEA, a well-tailored initialization operator and the NSGA-II structure are designed for global exploration in the first stage, and a competitive objective-based local search operator is developed to improve its local search ability and accelerate the convergence in the second stage. Extensive experiments based on fifty-eight newly formulated benchmarks are carried out to validate the effectiveness of the well-designed initialization operator and two-stage architecture. Comprehensive experiments are performed to evaluate the proposed PTEA, and the results reveal that the PTEA is superior to four comparison algorithms concerning the distribution, convergence, and overall performance.     

Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems

A linguistic-based meta-heuristic modeling and solution approach for solving the flexible job shop scheduling problem (FJSSP) is presented in this study. FJSSP is an extension of the classical job-shop scheduling problem. The problem definition is to assign each operation to a machine out of a set of capable machines (the routing problem) and to order the operations on the machines (the sequencing problem), such that predefined performance measures are optimized. In this research, the scope of the problem is widened by taking into account the alternative process plans for each part (process plan selection problem). Probabilistic selection of alternative process plans and machines are also considered. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls (Baykasolu, 2002). Using these controls and Giffler and Thompson's (1960) priority rule-based heuristic along with the multiple objective tabu search algorithm of Baykasolu et al. (1999) FJSSP is solved. This novel approach simplifies the modeling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its fast solution. Instead of scheduling job shops with inflexible algorithms that cannot take into account the flexibility which is available in the job shop, the present algorithm is developed which can take into account the flexibility during scheduling. Such an approach will considerably increase the responsiveness of the job shops.     

Flexible job shop scheduling under condition-based maintenance: Improved version of imperialist competitive algorithm

Maintenance activities have been ignored in many studies on scheduling problems where all machines are assumed to be available without interruption in the planning horizon. However, in realistic situations, they might be unavailable due to preventive maintenance, basic maintenance or unforeseen breakdowns. In this paper, we simulate a condition-based maintenance (CBM) for flexible job shop scheduling problem (FJSP) and consider the combination of Sigmoid function and Gaussian distribution to improve the CBM simulation. This study proposes an improved imperialist competitive algorithm (ICA) for the FJSP scheduling problem with the objective of the makespan minimization. The performance of the proposed algorithm is enhanced with a hybridization of ICA with simulated annealing (SA), after diagnosing standard ICA disadvantages and shortcomings. This ICA also includes a simulation part to handle CBM requirements. Various parameters of the novel ICA are reviewed to calibrate the algorithm with the help of the Taguchi experimental design. Experimental results show the high performance of the novel ICA in comparison with the standard ICA. The obtained results demonstrate that the novel ICA is an effective algorithm for FJSP under CBM. Finally, the performance of ICA is evaluated compared to other popular algorithms.     

A hybrid heuristic to solve the parallel machines job-shop scheduling problem

This paper presents an advanced software system for solving the flexible manufacturing systems (FMS) scheduling in a job-shop environment with routing flexibility, where the assignment of operations to identical parallel machines has to be managed, in addition to the traditional sequencing problem. Two of the most promising heuristics from nature for a wide class of combinatorial optimization problems, genetic algorithms (GA) and ant colony optimization (ACO), share data structures and co-evolve in parallel in order to improve the performance of the constituent algorithms. A modular approach is also adopted in order to obtain an easy scalable parallel evolutionary-ant colony framework. The performance of the proposed framework on properly designed benchmark problems is compared with effective GA and ACO approaches taken as algorithm components.