Routing and scheduling in a flexible job shop by tabu search

A hierarchical algorithm for the flexible job shop scheduling problem is described, based on the tabu search metaheuristic. Hierarchical strategies have been proposed in the literature for complex scheduling problems, and the tabu search metaheuristic, being able to cope with different memory levels, provides a natural background for the development of a hierarchical algorithm. For the case considered, a two level approach has been devised, based on the decomposition in a routing and a job shop scheduling subproblem, which is obtained by assigning each operation of each job to one among the equivalent machines. Both problems are tackled by tabu search. Coordination issues between the two hierarchical levels are considered. Unlike other hierarchical schemes, which are based on a one-way information flow, the one proposed here is based on a two-way information flow. This characteristic, together with the flexibility of local search strategies like tabu search, allows to adapt the same basic algorithm to different objective functions. Preliminary computational experience is reported.     

Solving the serial batching problem in job shop manufacturing systems

This paper addresses the serial batch scheduling problem embedded in a job shop environment to minimize makespan. Sequence dependent family setup times and a job availability assumption are also taken into account. In consideration of batching decisions, we propose a tabu search algorithm which consists of various neighborhood functions, multiple tabu lists and a sophisticated diversification structure. Computational experiments show that our algorithm outperforms a well-known tabu search approach which is developed for solving the traditional job shop problem. These results also confirm the benefits of batching.     

Cyclic job shop scheduling problems with blocking

A tabu search algorithm for a cyclic job shop problem with blocking is presented. Operations are blocking if they must stay on a machine after finishing when the next machine is occupied by another job. During this stay the machine is blocked for other jobs. For this problem traditional tabu search moves often lead to infeasible solutions. Recovering procedures are developed which construct nearby feasible solutions. Computational results are presented for the approach.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems

This paper deals with the no-wait job shop problem with a makespan objective. We present some new theoretical properties on the complexity of subproblems associated with a well-known decomposition approach. Justified by the complexity results, we implement a fast tabu search algorithm for the problem at hand. It is extensively tested on known benchmark instances and compares favorably to the best existing algorithms for the no-wait job shop as well as the no-wait flow shop.     

A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem

In this paper, we present a branch-and-bound approach for solving a two-machine flow shop scheduling problem, in which the objective is to minimize a weighted combination of job flowtime and schedule makespan. Experimental results show that the algorithm works very well for certain special cases and moderately well for others. In fact, it is able to produce optimal schedules for 500-job problems in which the second machine dominates the first machine. It is also shown that the algorithm developed to provide an upper bound for the branch-and-bound is optimal when processing times for jobs are the same on both machines. The primary reason for developing the branch-and-bound approach is that its results can be used to guide other heuristic techniques, such as simulated annealing, tabu search and genetic algorithms, in their search for optimal solutions for larger problems.     

A new neighborhood and tabu search for the Blocking Job Shop

The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.     

An integrated tabu search algorithm for the lot streaming problem in job shops

In this paper, we focus on solving the lot streaming problem in a job shop environment, where consistent sublots are considered. The presented three-phase algorithm incorporates the predetermination of sublot sizes, the determination of schedules based on tabu search and the variation of sublot sizes. With regard to tabu search implementation, a constructive multi-level neighbourhood is developed, which effectively connects three isolated neighbourhood functions. Moreover, enhancements of the basic version of tabu search are conducted. Combined with the procedure for varying sublot sizes, the algorithm further exploits the improvement potential. All tested instances show a rapid convergence to their lower bounds. The well-known difficult benchmark problems also achieve substantial makespan reduction. In addition, the performance of specific components is intensively examined in our study.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

Local search algorithms for the multiprocessor flow shop scheduling problem

The multiprocessor flow shop scheduling problem is a generalization of the ordinary flow shop scheduling problem. The problem consists of both assigning operations to machines and scheduling the operations assigned to the same machine. We review the literature on local search methods for flow shop and job shop scheduling and adapt them to the multiprocessor flow shop scheduling problem. Other local search approaches we consider are variable-depth search and simulated annealing. We show that tabu search and variable-depth search with a neighborhood originated by Nowicki and Smutnicki outperform the other algorithms.     

A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities

This paper presents a novel discrete artificial bee colony (DABC) algorithm for solving the multi-objective flexible job shop scheduling problem with maintenance activities. Performance criteria considered are the maximum completion time so called makespan, the total workload of machines and the workload of the critical machine. Unlike the original ABC algorithm, the proposed DABC algorithm presents a unique solution representation where a food source is represented by two discrete vectors and tabu search (TS) is applied to each food source to generate neighboring food sources for the employed bees, onlooker bees, and scout bees. An efficient initialization scheme is introduced to construct the initial population with a certain level of quality and diversity. A self-adaptive strategy is adopted to enable the DABC algorithm with learning ability for producing neighboring solutions in different promising regions whereas an external Pareto archive set is designed to record the non-dominated solutions found so far. Furthermore, a novel decoding method is also presented to tackle maintenance activities in schedules generated. The proposed DABC algorithm is tested on a set of the well-known benchmark instances from the existing literature. Through a detailed analysis of experimental results, the highly effective and efficient performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.     

Job Shop Scheduling with Tooling Constraints: a Tabu Search Approach

Flexible manufacturing systems (FMSs) are automated factories in which many different part types are produced simultaneously. The tool-loading problem now adds further to the delicate task of finding an optimal schedule for such systems. In this paper, a tabu search approach is developed to solve the job shop scheduling problem with tooling constraints.     

Bi-criteria group scheduling with sequence-dependent setup time in a flow shop

A bi-criteria group scheduling problem in a flow shop with sequence-dependent setup time is investigated in this paper. Manufacturing cell and flow shop are two popular scenarios in industry. Dynamic job releases and machine availabilities are assumed. The goal is to minimize the weighted sum of total weighted completion time and total weighted tardiness, which are aimed at satisfying the producer and customer goals separately. Normalized weights are assigned to both criteria to describe the trade-off between the two objectives. Two different initial solution finding mechanisms are proposed, and a tabu-search-based two-level search algorithm is deve1loped to find optimal/near-optimal solutions for the problem. A mathematical model is also developed and implemented to evaluate the optimality of the results from search algorithms for small problem instances. To further uncover the difference in performance of initial solutions and algorithms, an experimental design is performed and results are reported.     

An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem

This paper proposes a new tabu search algorithm for multi-objective combinatorial problems with the goal of obtaining a good approximation of the Pareto-optimal or efficient solutions. The algorithm works with several paths of solutions in parallel, each with its own tabu list, and the Pareto dominance concept is used to select solutions from the neighborhoods. In this way we obtain at each step a set of local nondominated points. The dispersion of points is achieved by a clustering procedure that groups together close points of this set and then selects the centroids of the clusters as search directions. A nice feature of this multi-objective algorithm is that it introduces only one additional parameter, namely, the number of paths. The algorithm is applied to the permutation flowshop scheduling problem in order to minimize the criteria of makespan and maximum tardiness. For instances involving two machines, the performance of the algorithm is tested against a Branch-and-Bound algorithm proposed in the literature, and for more than two machines it is compared with that of a tabu search algorithm and a genetic local search algorithm, both from the literature. Computational results show that the heuristic yields a better approximation than these algorithms.     

Computing lower and upper bounds for a large-scale industrial job shop scheduling problem

In this paper we present a case study from the lighting industry concerned with the scheduling of a set of job families each representing the production of a particular end-item in a given quantity. It is a job shop type problem, where each job family has a number of routing alternatives, and the solution has to respect batching and machine availability constraints. All jobs of the same job family have a common release date and a common due date, and they differ only in size. The objective is to minimize the total tardiness of the job families, rather than that of individual jobs. We propose a two-phase method based on solving a mixed-integer linear program and then improving the initial solution by tabu search. We evaluate our method on real-world as well as generated instances.     

A comparison of local search methods for flow shop scheduling

Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.     

Evolutionary Approaches to DNA Sequencing with Errors

In the paper, two evolutionary approaches to the general DNA sequencing problem, assuming both negative and positive errors in the spectrum, are compared. The older of them is based on the idea of genetic approach and is enhanced by a greedy algorithm. The newly proposed algorithm combines the tabu search and the scatter search methods. After conducting experiments with random and coding DNA sequences, our results suggest that the tabu and scatter search algorithm finds solutions of higher quality and more reliably than the genetic algorithm.     

Tabu search for discrete–continuous scheduling problems with heuristic continuous resource allocation

Problems of scheduling non-preemptable, independent jobs on parallel identical machines under an additional continuous renewable resource to minimize the makespan are considered. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. The processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic procedure for allocating the continuous resource is used. The tabu search metaheuristic to solve the considered problem is presented. The results produced by tabu search are compared with optimal solutions for small instances, as well as with the results generated by simple search methods – multi-start iterative improvement and random sampling for larger instances.     

A hybrid genetic algorithm for the job shop scheduling problem

This paper presents a hybrid genetic algorithm for the job shop scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.     

A tabu search approach for proportionate multiprocessor open shop scheduling

In the multiprocessor open shop scheduling problem, jobs are to be processed on a set of processing centers—each having one or more parallel identical machines, while jobs do not have a pre-specified obligatory route. A special case is the proportionate multiprocessor open shop scheduling problem (PMOSP) in which the processing time on a given center is not job-dependent. Applications of the PMOSP are evident in health care systems, maintenance and repair shops, and quality auditing and final inspection operations in industry. In this paper, a tabu search (TS) approach is presented for solving the PMOSP with the objective of minimizing the makespan. The TS approach utilizes a neighborhood search function that is defined over a network representation of feasible solutions. A set of 100 benchmark problems from the literature is used to evaluate the performance of the developed approach. Experimentations show that the developed approach outperforms a previously developed genetic algorithm as it produces solutions with an average of less than 5 % deviation from a lower bound, and 40 % of its solutions are provably optimal.