Solving the flow shop problem by parallel programming

The matter of using scheduling algorithms in parallel computing environments is discussed in this paper. There are proposed methods of parallelizing the criterion function calculations for a single solution and a group of concentrated solutions (local neighborhood) dedicated to being used in metaheuristic approaches. Also a parallel scatter-search metaheuristic is proposed as a multiple-thread approach. Computational experiments are done for the flow shop, the classic NP-hard problem of the combinatorial optimization.     

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.     

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 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 hybrid particle swarm optimization for job shop scheduling problem

A hybrid particle swarm optimization (PSO) for the job shop problem (JSP) is proposed in this paper. In previous research, PSO particles search solutions in a continuous solution space. Since the solution space of the JSP is discrete, we modified the particle position representation, particle movement, and particle velocity to better suit PSO for the JSP. We modified the particle position based on preference list-based representation, particle movement based on swap operator, and particle velocity based on the tabu list concept in our algorithm. Giffler and Thompson’s heuristic is used to decode a particle position into a schedule. Furthermore, we applied tabu search to improve the solution quality. The computational results show that the modified PSO performs better than the original design, and that the hybrid PSO is better than other traditional metaheuristics.     

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.     

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.     

Finding multiple solutions in job shop scheduling by niching genetic algorithms

The interest in multimodal optimization methods is increasing in the last years. The objective is to find multiple solutions that allow the expert to choose the solution that better adapts to the actual conditions. Niching methods extend genetic algorithms to domains that require the identification of multiple solutions. There are different niching genetic algorithms: sharing, clearing, crowding and sequential, etc. The aim of this study is to study the applicability and the behavior of several niching genetic algorithms in solving job shop scheduling problems, by establishing a criterion in the use of different methods according to the needs of the expert. We will experiment with different instances of this problem, analyzing the behavior of the algorithms from the efficacy and diversity points of view.     

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.     

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.     

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.     

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 hybrid immune simulated annealing algorithm for the job shop scheduling problem

A hybrid simulated annealing algorithm based on a novel immune mechanism is proposed for the job shop scheduling problem with the objective of minimizing total weighted tardiness. The proposed immune procedure is built on the following fundamental idea: the bottleneck jobs existing in each scheduling instance generally constitute the key factors in the attempt to improve the quality of final schedules, and thus, the sequencing of these jobs needs more intensive optimization. To quantitatively describe the bottleneck job distribution, we design a fuzzy inference system for evaluating the bottleneck level (i.e. the criticality) of each job. By combining the immune procedure with a simulated annealing algorithm, we design a hybrid optimization algorithm which is subsequently tested on a number of job shop instances. Computational results for different-sized instances show that the proposed hybrid algorithm performs effectively and converges fast to satisfactory solutions.     

A new hybrid genetic algorithm for job shop scheduling problem

Job shop scheduling problem is a typical NP-hard problem. To solve the job shop scheduling problem more effectively, some genetic operators were designed in this paper. In order to increase the diversity of the population, a mixed selection operator based on the fitness value and the concentration value was given. To make full use of the characteristics of the problem itself, new crossover operator based on the machine and mutation operator based on the critical path were specifically designed. To find the critical path, a new algorithm to find the critical path from schedule was presented. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed and its convergence was proved. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm.     

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.     

A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem

Job shop scheduling problem (JSP) which is widespread in the real-world production system is one of the most general and important problems in various scheduling problems. Nowadays, the effective method for JSP is a hot topic in research area of manufacturing system. JSP is a typical NP-hard combinatorial optimization problem and has a broad engineering application background. Due to the large and complicated solution space and process constraints, JSP is very difficult to find an optimal solution within a reasonable time even for small instances. In this paper, a hybrid particle swarm optimization algorithm (PSO) based on variable neighborhood search (VNS) has been proposed to solve this problem. In order to overcome the blind selection of neighborhood structures during the hybrid algorithm design, a new neighborhood structure evaluation method based on logistic model has been developed to guide the neighborhood structures selection. This method is utilized to evaluate the performance of different neighborhood structures. Then the neighborhood structures which have good performance are selected as the main neighborhood structures in VNS. Finally, a set of benchmark instances have been conducted to evaluate the performance of proposed hybrid algorithm and the comparisons among some other state-of-art reported algorithms are also presented. The experimental results show that the proposed hybrid algorithm has achieved good improvement on the optimization of JSP, which also verifies the effectiveness and efficiency of the proposed neighborhood structure evaluation method.     

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

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

带有跨工序约束的柔性job shop调度问题*

飞机制造企业的金属加工车间是一种小批量、多品种生产,其生产指挥是一种带有跨工序约束的柔性job shop调度问题。针对这个NP-hard问题,提出一种三阶段启发式方法,通过依次完成瓶颈工作中心的判定、设备分配和任务排序,使这一问题的复杂度得以逐步降低,从而可以在多项式时间内得到有效的调度方案。实际运行表明,依据该启发式方法产生的调度方案,其关键路径的等待时间占总完工时间的比例不足1.5%,取得了满意的效果。     

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.     

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.