Researches On Several Scheduling Problems Based On Metaheuristics

Scheduling problems is a form of decision-making that allocates limited resources to tasks and its goal is to optimize one or more objectives. It exists widely in most of the modern manufacturing and production industries. Optimized scheduling schemes are able to improve the production efficiency, reduce the production cost and hence bring better economic efficiency and market competitiveness for enterprises. Consequently, effective production scheduling is of great significance. Lots of scheduling problems is NP-hard from a complexity point of view, and classical scheduling algorithms such as heuristics and branch and bound methods face great difficulties for scheduling problems since they can hardly obtain the optimal solutions or they obtain the optimal solutions with great computational costs. Metaheuristics springing up recently are able to yield satisfactory scheduling schemes without complex mathematical formulations and it is a kind of simple yet powerful method for scheduling problems. This dissertation analyses several scheduling problems and proposed several metaheuristics for solving these scheduling problems. Moreover, the researches extend to stochastic scheduling problems where the processing times are subjected to stochastic distributions. The main contributions of this dissertation are listed below.(1) To minimize the total weighted tardiness for the single machine scheduling problem with sequence-dependent setup times, some elimination rules and speed-ups are presented for the swap move, and an enhanced iterated greedy (EIG) algorithm is proposed. The elimination rules and speed-ups are presented for the first time and employed in the EIG algorithm. Besides, the EIG algorithm incorporates a novel perturbation operator, best insert procedure, to prevent the search from being attracted to local optima. Experimental results based on a benchmark set show that the proposed EIG algorithm outperforms several state-of-the-art metaheuristics.(2) A hybrid discrete differential evolution (HDDE) algorithm is presented for the identical parallel machine scheduling problem to minimize the total tardiness. Inspired by the branch and bound methods in the literature, we employ the job permutation as the coding and decoding scheme and present a discrete differential evolution algorithm. Moreover, an improved local search procedure is incorporated in the algorithm. Experimental results based on a benchmark set show that the proposed HDDE algorithm outperforms the discrete differential evolution algorithm and a hybrid particle swarm optimization algorithm, and it has advantages over the state-of-the-art branch and bound method in computational time and problem size.(3) To solve the no-idle flow shop scheduling problem with makespan criterion, a speed-up method is presented for the insert neighborhood, and a hybrid discrete differential evolution (HDDE) algorithm is proposed. The speed-up method is based on the network representation and can reduce the time complexity of evaluating the whole insert neighborhood from O(mn3) to O(mn2), where m and n are the machine number and job number respectively. A perturbed local search which uses the speed-up method is applied in the HDDE algorithm to balance global exploration and local exploitation. An extensive computational campaign is conducted on a benchmark set. Results indicate that the speed-up method can greatly reduce the computational expenses, and the proposed HDDE algorithm outperforms several state-of-the-art metaheuristics.(4) A discrete artificial bee colony (DABC) algorithm is proposed for the flow shop scheduling problem with intermediate buffers. Firstly, the solution in the algorithm is represented as job permutation. Secondly, an initialization scheme based on heuristics and a local search is designed to construct the initial population with both quality and diversity. Thirdly, the newly designed schemes for employed bee, onlooker bee and scout bee are presented. Experimental results based on a benchmark set show that the DABC algorithm is feasible and effective for the flow shop scheduling problem with intermediate buffers to minimize makespan and total flow time, respectively.(5) Regarding the stochastic flow shop scheduling problem, the no-idle flow shop scheduling problem where the processing times are subjected to exponential distributions is considered, and the stochastic expected value model is developed for the problem. The HDDE algorithm in (3) is adapted to the stochastic expected value model, and experimental results validate the effectiveness of the HDDE algorithm.