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.     

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.     

Ant colony optimization combined with taboo search for the job shop scheduling problem

In this paper, we present a hybrid algorithm combining ant colony optimization algorithm with the taboo search algorithm for the classical job shop scheduling problem. Instead of using the conventional construction approach to construct feasible schedules, the proposed ant colony optimization algorithm employs a novel decomposition method inspired by the shifting bottleneck procedure, and a mechanism of occasional reoptimizations of partial schedules. Besides, a taboo search algorithm is embedded to improve the solution quality. We run the proposed algorithm on 101 benchmark instances and obtain competitive results and a new best upper bound for one open benchmark instance is found.     

On the connection between a cyclic job shop and a reentrant flow shop scheduling problem

Hall et al. (J. Sched. 2002; 5:307–327) investigated the cycle time minimization problem in a two-machine job shop, where each job consists of at most three operations. In this note, we reduce the problem to a two-machine reentrant flow shop problem and briefly discuss some consequences.     

Job-shop scheduling using neural networks

Job-shop scheduling cannot easily be analytically accomplished, so, it is done by computer simulation using heuristic priority rules. The SLACK rule for calculating the margins of jobs to their due-dates is effective in meeting the due-dates. However, the calculated margins are not precise because the actual margin is shortened due to conflicts with other jobs. The authors propose a method for estimating the margins by using a neural network. It is found that the method is effective for improving the average lateness to due-dates but not the maximum lateness. This paper proposes a method for adding a second neural network for judging the reliability of the estimated margins composed to the first one and for switching to the margins calculated by the SLACK rule when the reliability is low. The proposed method is verified by scheduling simulations to be effective in decreasing the maximum lateness to due-dates as much as the average lateness.     

Mathematical models for preemptive shop scheduling problems

More than half a century has passed since Bowman and Dantzig (1959) [13] and [14] introduced their models for preemptive shop scheduling problems. A more efficient model seems to be needed to address all the aspects involved in the problem. We introduce a new Integer Linear Programming (ILP) formulation as a new method for solving the preemptive Job Shop Scheduling Problem (pJSSP). The dimension of the new model, unlike those of the existing ones, depends solely on the number of jobs and machines irrespective of processing times. The proposed model is used as an optimal, two-phase approach. In phase one, the model is solved to obtain the start and completion times of each operation on each machine. In phase two, a simple algorithm in O(mn log n) steps is used to turn these times into a complete and optimal schedule. Different preemptive flow shop problems are studied as special cases of the pJSSP while some related properties are also discussed. Finally, the higher efficiency of the proposed model is verified both theoretically and computationally through its comparison with conventional methods commonly in use.     

Applying a hybrid job shop procedure to a Belgian manufacturing company producing industrial wheels and castors in rubber

In this paper, several methods for job shop scheduling are combined, adjusted and successfully applied to a real-world scheduling problem at a Belgian manufacturer producing industrial wheels and castors in rubber. The procedure is an extension of a hybrid shifting bottleneck procedure with a tabu search algorithm while incorporating various company specific constraints. The various extensions to cope with the company specific constraints have a strong similarity with the complex job shop problem formulation of Mason, Fowler, and Carlyle (2002). The new procedure is used as a simulation engine to test the relevance of various scenarios in order to improve the current planning approach of the company. A detailed computational experiment highlights the main contribution of the novel procedure for the company.     

Scheduling trains as a blocking parallel-machine job shop scheduling problem

In this paper, the train scheduling problem is modelled as a blocking parallel-machine job shop scheduling (BPMJSS) problem. In the model, trains, single-track sections and multiple-track sections, respectively, are synonymous with jobs, single machines and parallel machines, and an operation is regarded as the movement/traversal of a train across a section. Due to the lack of buffer space, the real-life case should consider blocking or hold-while-wait constraints, which means that a track section cannot release and must hold the train until next section on the routing becomes available. Based on literature review and our analysis, it is very hard to find a feasible complete schedule directly for BPMJSS problems. Firstly, a parallel-machine job-shop-scheduling (PMJSS) problem is solved by an improved shifting bottleneck procedure (SBP) algorithm without considering blocking conditions. Inspired by the proposed SBP algorithm, feasibility satisfaction procedure (FSP) algorithm is developed to solve and analyse the BPMJSS problem, by an alternative graph model that is an extension of the classical disjunctive graph models. The proposed algorithms have been implemented and validated using real-world data from Queensland Rail. Sensitivity analysis has been applied by considering train length, upgrading track sections, increasing train speed and changing bottleneck sections. The outcomes show that the proposed methodology would be a very useful tool for the real-life train scheduling problems.     

An immunoglobulin-based artificial immune system for solving the hybrid flow shop problem

We consider the n-job, k-stage problem in a hybrid flow shop (HFS) with the objective of minimizing the maximum completion time, or makespan, which is an NP-hard problem. An immunoglobulin-based artificial immune system algorithm, called IAIS algorithm, is developed to search for the best sequence. IAIS, which is better fit the natural immune system, improves the existing AIS by the process before/after encounter with antigens. Before encounter with antigens, a new method of somatic recombination is presented; after encounter with antigens, an isotype switching is proposed. The isotype switching is a new approach in artificial immune system, and its purpose is to produce antibodies with the same protection but different function to defense the antigen. To verify IAIS, comparisons with the existing immune-based algorithms and other non-immune-based algorithms are made. Computational results show that IAIS is very competitive for the hybrid flow shop scheduling problem.     

蚂蚁算法在车间作业调度问题中的应用

蚂蚁算法是近年来新出现的一种随机型搜索寻优算法,自从在TSP等著名问题中得到富有成效的应用之后,已引起越来越多的关注和重视。论文进一步将这种新型的生物优化思想进行扩展,提出了一种解决车间作业调度问题(JSSP:JobShopSchedulingProblem)的蚂蚁优化算法,给出了求解的一般步骤和流程。通过计算实例的结果,说明了该算法优于传统算法。     

An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

Mathematical model and genetic optimization for the job shop scheduling problem in a mixed- and multi-product assembly environment: A case study based on the apparel industry

An effective job shop scheduling (JSS) in the manufacturing industry is helpful to meet the production demand and reduce the production cost, and to improve the ability to compete in the ever increasing volatile market demanding multiple products. In this paper, a universal mathematical model of the JSS problem for apparel assembly process is constructed. The objective of this model is to minimize the total penalties of earliness and tardiness by deciding when to start each order’s production and how to assign the operations to machines (operators). A genetic optimization process is then presented to solve this model, in which a new chromosome representation, a heuristic initialization process and modified crossover and mutation operators are proposed. Three experiments using industrial data are illustrated to evaluate the performance of the proposed method. The experimental results demonstrate the effectiveness of the proposed algorithm to solve the JSS problem in a mixed- and multi-product assembly environment.     

A heuristic for job shop scheduling to minimize total weighted tardiness

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.     

A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.     

基于启发式规则和蚁群算法的车间作业调度方法

车间作业调度问题是一个典型的NP-hard问题,也是一个前沿性的研究课题,已受到学术界和工业界的广泛关注。提出了一种基于启发式规则和蚁群算法的车间作业调度方法。该方法首先采用蚁群算法得到车间作业调度问题的一组可行解,然后采用一些启发式规则进一步优化这些可行解。通过将启发式规则有效地融入到蚁群算法中,使得该混合方法的优化效率得到极大的改进。仿真实例表明,方法是可行的、正确的和有效的。     

Improving the delivery efficiency of the customer order scheduling problem in a job shop

The focus of this paper is customer order scheduling (COS) problem, where each order consists of a set of jobs that must be shipped as one batch at the same time. In COS each job is part of a customer order and the make-up of the jobs in the order are pre-specified. Most of the existing research deals with COS in a single machine or in a parallel machine shop for developing an optimal solution. COS is common in a normal job shop, and the more complex the shop, the more complex the scheduling. Most existing research has focused on trying to reduce the completion time of the batch. That is, the focus is only on the point in time the last job is finished, while ignoring the actual duration of the jobs within the same order. The longer it takes to complete all the jobs within an order the more it increases the stock of finished goods and the more it deteriorates the efficiency of the logistics and the supply chain management.A new dispatching rule, referred to as Minimum Flow Time Variation (MFV), has been proposed for COS in a normal job shop, in order to reduce the total time it takes to complete all jobs within the same order. That is, the individual completion times of all jobs for the same customer order will be controlled in order to improve the shipping performance. In the simulation test and statistical analysis, the level of work in process (WIP) under the MFV rule in the finished goods warehouse is reduced by more than 70% compared to any other method. The MFV method will efficiently reduce the stock level of finished goods, and controls the waiting time required before they can be shipped. Depending on the environmental factors, the performance of our proposed method will become increasingly significant the more complex the system.     

Scheduling image processing tasks in a multilayer system

Multilayer multiprocessor systems are generally employed in real-time applications such as robotics and computer vision. This paper introduces three heuristic algorithms for multiprocessor task scheduling in such systems. In our model, tasks with arbitrary processing times and arbitrary processor requirements are considered. The scheduling aims at minimising completion time of processes in a two-layer system. We employed an effective lower bound (LB) for the problem. Then, we analysed the average performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the LB on a set of randomly generated problems. We have also applied these algorithms for scheduling computer vision tasks running on prototype multilayer architecture. Our computational and empirical results showed that the proposed heuristic algorithms perform well.