Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time

This paper focuses on the distributed two-stage assembly flowshop scheduling problem for minimising a weighted sum of makespan and mean completion time. This problem involves two inter-dependent decision sub-problems: (1) how to allocate jobs among factories and (2) how to schedule the assigned jobs at each factory. A mathematical model is formulated for solving the small-sized instances of the problem. Since the NP-hardness of the problem, we also proposed a variable neighbourhood search (VNS) algorithm and a hybrid genetic algorithm combined with reduced variable neighbourhood search (GA-RVNS) to solve the distributed two-stage assembly flowshop scheduling problems and approximately optimise makespan and mean completion time simultaneously. Computational experiments have been conducted to compare the performances of the model and proposed algorithms. For a set of small-sized instances, both the model and the proposed algorithms are effective. The proposed algorithms are further evaluated on a set of large-sized instances. The results statistically show that both GA-RVNS and VNS obtain much better performances than the GA without RVNS-based local search step (GA-NOV). For the instances with small numbers of jobs, VNS achieves better performances than GA-RVNS. However, for the instances with large numbers of jobs, GA-RVNS yields better performances than the VNS. It is also shown that the overall performances of VNS are very close to GA-RVNS with different numbers of factories, weights given to makespan and numbers of machines at the first stage.     

Variable neighbourhood search for dual-resource constrained flexible job shop scheduling

Dual-resource constrained flexible job shop scheduling problem (FJSP) is considered and an effective variable neighbourhood search (VNS) is presented, in which the solution to the problem is indicated as a quadruple string of the ordered operations and their resources. Two neighbourhood search procedures are sequentially executed to produce new solutions for two sub-problems of the problem, respectively. The search of VNS is restarted from a slightly perturbed version of the current solution of VNS when the determined number of iterations is reached. VNS is tested on some instances and compared with methods from literature. Computational results show the significant advantage of VNS on the problem.     

A robust optimization approach for integrated steel production and batch delivery scheduling with uncertain rolling times and deterioration effect

Efficient collaboration between various sub-processes of steel production is of considerable significance, which directly affects a product’s production cycle and energy consumption. However, current collaborative optimisation models and methods in steel production are still limited: (1) Most of the current collaborative manufacturing problems in steel production focus on obtaining joint schedule between steel-making and continuous casting (SCC), and the works considering continuous casting and hot rolling (CCHR) are very few. (2) The processing time is assumed as a constant in most of the existing SCC scheduling models. However, the rolling time of a product in hot rolling operation is actually uncertain and deteriorating. (3) Exact algorithms cannot be applied to solve the complicated collaborative optimisation problems because of their high complexities. To address these problems, we propose an integrated CCHR and batch delivery scheduling model where interval rolling time and linear deterioration effect are considered. With the concept of min–max regret value, we formulate the collaborative optimisation problem as a robust optimisation problem. Instead of using the exact algorithm, we develop an Improved Variable Neighborhood Search (IVNS) algorithm incorporated a novel population update mechanism and neighbourhood structures to solve the robust optimisation problem. Moreover, we develop an exact algorithm that combines CPLEX solver and two dynamic programming algorithms to obtain the maximum regret value of a given rolling sequence. The results of computational experiments show the excellent performance of the proposed algorithms.

Abbreviations: IVNS: improved variable neighbourhood search; TOPSIS: technique for order of preference by similarity to ideal solution; PUM-TOPSIS: population update mechanism based on TOPSIS; DP: dynamic programming; NSs-PUC: neighbourhood structures based on the parameterised uniform crossover; SNRT: shortest normal rolling time; SNRT-DP: DP algorithm based on SNRT rule; BRKGA: biased random-key genetic algorithm; SCC: steelmaking and continuous casting; MINP: mixed integer nonlinear programme; CCHR: continuous casting and hot rolling; PSO: particle swarm optimisation; GA: genetic algorithm; VNS-HS: variable neighbourhood search and harmony search; HPSO?+?GA: hybrid PSO and GA; SA: simulated annealing; B&B: branch-and-bound; TPSO: two-phase soft optimisation; TSAUN: tabued simulated annealing with united-scenario neighbourhood; VNS: variable neighbourhood search; ABC: artificial bee colony; PRVNS: population-based reduced variable neighbourhood search; NS1: neighbourhood structure 1; NS2: neighbourhood structure 2; DE: differential evolution; WSR: Wilcoxon signed-rank test; ENS: exchange neighbourhood structure; IVNS-ENS: IVNS with ENS; RPI: relative percentage increase; ARPI: average RPI; SD: standard deviation.     

Coordinated scheduling of production and transportation in a two-stage assembly flowshop

To enhance the overall performance of supply chains, coordination among production and distribution stages has recently received an increasing interest. This paper considers the coordinated scheduling of production and transportation in a two-stage assembly flowshop environment. In this problem, product components are first produced and assembled in a two-stage assembly flowshop, and then completed final products are delivered to a customer in batches. Considering the NP-hard nature of this scheduling problem, two fast heuristics (SPT-based heuristic and LPT-based heuristic) and a new hybrid meta-heuristic (HGA-OVNS) are presented to minimise the weighted sum of average arrival time at the customer and total delivery cost. To guide the search process to more promising areas, the proposed HGA-OVNS integrates genetic algorithm with variable neighbourhood search (VNS) to generate the offspring individuals. Furthermore, to enhance the effectiveness of VNS, the opposition-based learning (OBL) is applied to establish some novel opposite neighbourhood structures. The proposed algorithms are validated on a set of randomly generated instances, and the computation results indicate the superiority of HGA-OVNS in quality of solutions.     

A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel VNS execution

This paper addresses the flexible-job-shop scheduling problem (FJSP) with the objective of minimising total tardiness. FJSP is the generalisation of the classical job-shop scheduling problem. The difference is that in the FJSP problem, the operations associated with a job can be processed on any set of alternative machines. We developed a new algorithm by hybridising genetic algorithm and variable neighbourhood search (VNS). The genetic algorithm uses advanced crossover and mutation operators to adapt the chromosome structure and the characteristics of the problem. Parallel-executed VNS algorithm is used in the elitist selection phase of the GA. Local search in VNS uses assignment of operations to alternative machines and changing of the order of the selected operation on the assigned machine to increase the result quality while maintaining feasibility. The purpose of parallelisation in the VNS algorithm is to minimise execution time. The performance of the proposed method is validated by numerical experiments on several representative problems and compared with adapted constructive heuristic algorithms’ (earliest due date, critical ratio and slack time per remaining operation) results.     

A variable neighbourhood search algorithm for the flexible job-shop scheduling problem

The flexible job-shop scheduling problem (FJSP) is a generalisation of the classical job-shop scheduling problem which allows an operation of each job to be executed by any machine out of a set of available machines. FJSP consists of two sub-problems which are assigning each operation to a machine out of a set of capable machines (routing sub-problem) and sequencing the assigned operations on the machines (sequencing sub-problem). This paper proposes a variable neighbourhood search (VNS) algorithm that solves the FJSP to minimise makespan. In the process of the presented algorithm, various neighbourhood structures related to assignment and sequencing problems are used for generating neighbouring solutions. To compare our algorithm with previous ones, an extensive computational study on 181 benchmark problems has been conducted. The results obtained from the presented algorithm are quite comparable to those obtained by the best-known algorithms for FJSP.     

An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem

The permutation flowshop scheduling problem (PFSP) has been extensively studied in the scheduling literature. In this paper, we present an improved memetic algorithm (MA) to solve the PFSP to minimise the total flowtime. In the proposed MA, we develop a stochastic local search based on a dynamic neighbourhood derived from the NEH method. During the evolution process, the size of the neighbourhood is dynamically adjusted to change the search focus from exploration to exploitation. In addition, we introduce a new population generation mechanism to guarantee both the quality and diversity of the new populations. We also design a diversity index for the population to monitor the diversity of the current population. If the diversity index is less than a given threshold value, the current population will be replaced by a new one with good diversity so that the proposed MA has good ability to overcome local optima. We conduct computational experiments to test the effectiveness of the proposed algorithm. The computational results on randomly generated problem instances and benchmark problem instances show that the proposed MA is effective and superior or comparable to other algorithms in the literature.     

Dynamic job shop scheduling using variable neighbourhood search

In this paper a scheduling method based on variable neighbourhood search (VNS) is introduced to address a dynamic job shop scheduling problem that considers random job arrivals and machine breakdowns. To deal with the dynamic nature of the problem, an event-driven policy is selected. To enhance the efficiency and effectiveness of the scheduling method, an artificial neural network with a back propagation error learning algorithm is used to update parameters of the VNS at any rescheduling point according to the problem condition. The proposed method is compared with some common dispatching rules that have been widely used in the literature for the dynamic job shop scheduling problem. Results illustrate the high efficiency and effectiveness of the proposed method in a variety of shop floor conditions.     

A variable neighbourhood search for integrated production and preventive maintenance planning in multi-state systems

This paper presents a variable neighbourhood search (VNS) to the integrated production and maintenance planning problem in multi-state systems. VNS is one of the most recent meta-heuristics used for problem solving in which a systematic change of neighbourhood within a local search is carried out. In the studied problem, production and maintenance decisions are co-ordinated, so that the total expected cost is minimised. We are given a set of products that must be produced in lots on a multi-state production system during a specified finite planning horizon. Planned preventive maintenance and unplanned corrective maintenance can be performed on each component of the multi-state system. The maintenance policy suggests cyclical preventive replacements of components, and a minimal repair on failed components. The objective is to determine an integrated lot-sizing and preventive maintenance strategy of the system that will minimise the sum of preventive and corrective maintenance costs, setup costs, holding costs, backorder costs and production costs, while satisfying the demand for all products over the entire horizon. We model the production system as a multi-state system with binary-state components. The formulated problem can be solved by comparing the results of several multi-product capacitated lot-sizing problems. The proposed VNS deals with the preventive maintenance selection task. Results on test instances show that the VNS method provides a competitive solution quality at economically computational expense in comparison with genetic algorithms.     

On the integrated charge planning with flexible jobs in primary steelmaking processes

The integrated charge planning (ICP) problem based on flexible jobs in an integrated steel plant is extremely difficult and valuable. The purpose of this paper is to improve the efficiency and feasibility of planning by minimising the number of charges, minimising the total production costs and maximising the total throughput, considering the hard constraints and soft constraints. A multi-objective mathematical programming model for the problem is formulated, and it is shown that the problem is NP-hard. Two new meta-heuristics are designed, one is guided variable neighbourhood search (GVNS) combined with harmony search, and the other is GVNS combined with simulated annealing. Compared with enumeration algorithm, tabu search, variable neighbourhood search (VNS), harmony search, extend next fit decreasing (ENFD) and skewed VNS (SVNS), variable neighbourhood descent (VND), the numerical results by actual production data have shown that the proposed model and GVNHS are feasible and effective for ICP.     

Variable neighbourhood search for minimising tardiness objectives on flow shop with batch processing machines

This paper presents the scheduling problem on flow shop with many batch processing machines (BPM) to minimise total tardiness, maximum tardiness and number of tardy jobs, respectively. We propose an efficient variable neighbourhood search (VNS) for the problem, in which job permutation is the only optimisation object and the solutions of batch formation and batch scheduling can be directly obtained by using the permutation. To obtain the promising results, an initial solution of VNS is first produced and then one insertion operation and two swap operations are applied to improve the solution. The proposed VNS is finally tested and the computational results show its good performance on many-BPM flow shop scheduling.     

Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems

This article presents the variable neighbourhood simulated annealing (VNSA) algorithm, a variant of the variable neighbourhood search (VNS) combined with simulated annealing (SA), for efficiently solving capacitated vehicle routing problems (CVRPs). In the new algorithm, the deterministic ‘Move or not’ criterion of the original VNS algorithm regarding the incumbent replacement is replaced by an SA probability, and the neighbourhood shifting of the original VNS (from near to far by k← k+1) is replaced by a neighbourhood shaking procedure following a specified rule. The geographical neighbourhood structure is introduced in constructing the neighbourhood structures for the CVRP of the string model. The proposed algorithm is tested against 39 well-known benchmark CVRP instances of different scales (small/middle, large, very large). The results show that the VNSA algorithm outperforms most existing algorithms in terms of computational effectiveness and efficiency, showing good performance in solving large and very large CVRPs.     

A hybrid electromagnetism-like algorithm for two-stage assembly flow shop scheduling problem

This paper presents a study on the two-stage assembly flow shop scheduling problem for minimising the weighed sum of maximum makespan, earliness and lateness. There are m machines at the first stage, each of which produces a component of a job. A single machine at the second stage assembles the m components together to complete the job. A novel model for solving the scheduling problem is built to optimise the maximum makespan, earliness and lateness simultaneously. Two optimal operation sequences of jobs are determined and verified. As the problem is known to be NP-hard, a hybrid variable neighbourhood search – electromagnetism-like mechanism (VNS-EM) algorithm is proposed for its handling. To search beyond local optima for a global one, VNS algorithm is embedded in each iteration of EM, whereby the fine neighbourhood search of optimum individuals can be realised and the solution is thus optimised. Simulation results show that the proposed hybrid VNS-EM algorithm outperforms the EM and VNS algorithms in both average value and standard deviation.     

产品配置中相似实例模糊优选法的研究

分析了传统BOM在产品种类剧增的大规模定制竞争环境下的缺陷，阐明了面向产品族的创成式BOM（Generic Bill-of-material,GBOM)的概念。研究了GBOM的面向对象表达方法以及基于GBOM的产品配置过程，提出采用模糊优选法解决配置过程中相似实例的提取问题，并给出基本算法和实例验证，最后讨论了GBOM树中零部件类节点相似实例提取中的关键问题及解决方法。     

A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems

This paper presents a hybrid Pareto-based local search (PLS) algorithm for solving the multi-objective flexible job shop scheduling problem. Three minimisation objectives are considered simultaneously, i.e. the maximum completion time (makespan), the total workload of all machines, and the workload of the critical machine. In this study, several well-designed neighbouring approaches are proposed, which consider the problem characteristics and thus can hold fast convergence ability while keep the population with a certain level of quality and diversity. Moreover, a variable neighbourhood search (VNS) based self-adaptive strategy is embedded in the hybrid algorithm to utilise the neighbouring approaches efficiently. Then, an external Pareto archive is developed to record the non-dominated solutions found so far. In addition, a speed-up method is devised to update the Pareto archive set. Experimental results on several well-known benchmarks show the efficiency of the proposed hybrid algorithm. It is concluded that the PLS algorithm is superior to the very recent algorithms, in term of both search quality and computational efficiency.     

A reliability/availability approach to joint production and maintenance scheduling with multiple preventive maintenance services

In classical scheduling problems, it is often assumed that the machines are available during the whole planning horizon, while in realistic environments, machines need to be maintained and therefore may become unavailable within production periods. Hence, in this paper we suggest a joint production and maintenance scheduling (JPMS) with multiple preventive maintenance services, in which the reliability/availability approach is employed to model the maintenance aspects of a problem. To cope with the suggested JPMS, a mixed integer nonlinear programming model is developed and then a population-based variable neighbourhood search (PVNS) algorithm is devised for a solution method. In order to enhance the search diversification of basic variable neighbourhood search (VNS), our PVNS uses an epitome-based mechanism in each iteration to transform a group of initial individuals into a new solution, and then multiple trial solutions are generated in the shaking stage for a given solution. At the end of the local search stage, the best obtained solution by all of the trial solutions is recorded and the worst solution in population is replaced with this new solution. The evolution procedure is continued until a predefined number of iterations is violated. To validate the effectiveness and robustness of PVNS, an extensive computational study is implemented and the simulation results reveal that our PVNS performs better than traditional algorithms, especially in large size problems.     

A GRASP algorithm for flexible job-shop scheduling problem with limited resource constraints

A greedy randomised adaptive search procedure (GRASP) is an iterative multi-start metaheuristic for difficult combinatorial optimisation. The GRASP iteration consists of two phases: a construction phase, in which a feasible solution is found and a local search phase, in which a local optimum in the neighbourhood of the constructed solution is sought. In this paper, a GRASP algorithm is presented to solve the flexible job-shop scheduling problem (FJSSP) with limited resource constraints. The main constraint of this scheduling problem is that each operation of a job must follow an appointed process order and each operation must be processed on an appointed machine. These constraints are used to balance between the resource limitation and machine flexibility. The model objectives are the minimisation of makespan, maximum workload and total workload. Representative benchmark problems are solved in order to test the effectiveness and efficiency of the GRASP algorithm. The computational result shows that the proposed algorithm produced better results than other authors’ algorithms.     

An efficient iterated local search algorithm for the total tardiness blocking flow shop problem

This paper deals with the blocking flow shop problem and proposes an Iterated Local Search (ILS) procedure combined with a variable neighbourhood search (VNS) for the total tardiness minimisation. The proposed ILS makes use of a NEH-based procedure to generate the initial solution, and uses a local search to intensify the exploration that combines the insertion and swap neighbourhood and uses a perturbation mechanism consisting of three neighbourhood operators to diversify the search. The computational evaluation has shown the effectiveness of combining the insertion and swap neighbourhood during the search despite the insertion neighbourhood being more effective than the swap neighbourhood for this problem. Finally, the computation of this algorithm when evaluated against two other algorithms from the literature shows good performance.     

A multi-objective flow shop scheduling with resource-dependent processing times: trade-off between makespan and cost of resources

In traditional flow shop scheduling problems (FSSPs), the processing times are assumed to be pre-known and fixed parameters while in many practical environments, the processing times can be controlled by consumption of extra resources. In this paper, we propose resource-dependent processing times (RDPT) for permutation FSSP in which the processing time of a job depends on the amount of additional resources assigned to that job. To make a trade-off between makespan and required amount of resources, two conflict objective functions are considered: the minimisation of maximum completion time and the minimisation of total cost of resources. In order to solve the problem considered in this paper, a decomposition approach is suggested that strives to deal with the original model via two sub-problems: (i) sequencing problem; and (ii) resource allocation problem. A hybrid discrete differential evolution (HDDE) algorithm with an effective coordinate directions search and a variable neighbourhood search (VNS) are combined to solve two sub-problems. Furthermore, a statistical procedure is employed to adjust the significant parameters of the proposed HDDE and VNS algorithms. This procedure is based on the stepwise regression (SR) technique. The effectiveness of the suggested hybrid algorithm is investigated through a computational study and obtained results show the good performance of our approach with regard to the other algorithms.     

A hybrid VNS-HS algorithm for a supply chain scheduling problem with deteriorating jobs

This paper investigates a coordinated scheduling problem in a two stage supply chain where parallel-batching machine, deteriorating jobs and transportation coordination are considered simultaneously. During the production stage, jobs are processed by suppliers and there exists one parallel-batching machine in each supplier. The actual processing time of a job depends on its starting time and normal processing time. The normal processing time of a batch is equal to the largest normal processing time among all jobs in its batch. During the transportation stage, the jobs are then delivered to the manufacturer. Since suppliers are distributed in different locations, the transportation time between each supplier and the manufacturer is different. Based on some structural properties of the studied problem, an optimal algorithm for minimising makespan on a single supplier is presented. This supply chain scheduling problem is proved to be NP-hard, and a hybrid VNS-HS algorithm combining variable neighbourhood search (VNS) with harmony search (HS) is proposed to find a good solution in reasonable time. Finally, some computational experiments are conducted and the results demonstrate the effectiveness and efficiency of the proposed VNS-HS.