Research On Key-Machine Scheduling Problems With Consideration Of Engery Conservation

Most classical scheduling problems assume that the parameters such as job release dates and processing times are constant. However, in some high-energy-consuming industries, especially in metallurgy or chemical industry, the values of the parameters maybe depend on the amount of energy consumption and at the same time affect the scheduling results. Therefore it is necessary to balance the conflict between the production efficiency and the energy consumption in key-machine scheduling problems of these industries.This dissertation firstly researches on the multi-key-machine scheduling problem without consideration of energy consumption. On this basis it researches on three multi-key-machine scheduling problems with energy consumption constraints, including the multi-key-machine scheduling problem with energy dependent release dates, the multi-key-machine scheduling problem with energy constrained processing times and the multi-key-machine scheduling problem in which the job release dates and processing times are simultaneously dependent on energy consumption. Because these problems are all NP-hard and can not be solved exactly in polynomial time, lower bounds are designed to evaluate the accuracy of the solutions. The meta-heuristic algorithms are presented to obtain near-optimal solutions with high quality in a reasonable time.The main contributions of this dissertation are listed as follows.(1) The dissertation first researches on the multi-key-machine scheduling problem without consideration of energy consumption constraints on both release date and processing time. The purpose of the scheduling problem is to minimize the makespan. It analyses the advantages and disadvantages of the existing LPT-ECT algorithm and the Koulamas & Kyparisis's algorithm, and proposes a modified MLPT algorithm. Based on the characteristics of the optimal solutions of the problem, it designs a new solution presentation method, which can not only effectively simplify the implement of the insertion and swap neighborhood, but also narrow the solution space. It further improves the accuracy of the solution through variable neighborhood search and simulated annealing algorithm. It constructs a large number of random data experiments, considering 10 different distributions of job release date. Experimental studies show the proposed simulated annealing algorithm can make the average relative error converging to 0.363%. For a special case of this problem, in which jobs have the same release date and machines have the same speed, the accuracy and efficiency of the proposed simulated annealing algorithm are obviously superior to the existing simulated annealing algorithm proposed by Lee et al. (2) It researches on the multi-key-machine scheduling problem with energy consumption constraint on the release dates of jobs. The scheduling purpose is to minimize the energy consumption under a given makespan. It assumes that the energy consumption dependent functions of the release dates are general decreasing functions. It gives a formal description of the problem, analyses the potential characteristics of the optimal solutions of the problem, designs two basic operations of left-move and right-move of the task, discusses how to calculate the total energy consumption influenced by the swap and insert neighborhood, and designs a variable neighborhood search algorithm and simulated annealing algorithm for the problem. To evaluate the accuracy of the solutions, it relaxes the corresponding relationship between the job start time and its energy consumption dependent function, thereby obtaining an assignment problem. It uses the Hungary method to obtain the optimal solution of the relaxation problem, and designs a lower bound for the original problem. It tests the performance of the algorithm by a great deal of experiments, taking the linear energy consumption dependent function as example. Moreover, when solving the single key machine scheduling problems with linear and convex decreasing energy consumption dependent functions respectively, the accuracy of simulated annealing algorithm is superior to the existing algorithms proposed by Janiak and Kaspi & Shabtay.(3) It researches on the multi-key-machine scheduling problem with the energy constrained processing times. The purpose of the scheduling is to minimize the makespan under the constraint of given total energy. It gives the formal description of the problem of general decreasing constraint function of the energy consumption and analyses the potential characteristics of the optimal solutions. To design a fast simulated annealing algorithm, it presents the definitions of determine machine and non-determine machine, and optimizes the local solution consisting of a certain determine machine and the non-determine machine with the minimum maximal complete time. The process of search aims to optimize the local solution, and therefore the search is typically narrow targeted. To solve the problem with linear energy consumption functions, the proposed simulated annealing algorithm can solve the problem consisting of 1000 jobs in 0.875 second and hold the relative error within 0.019946%. To solve the problem of convex decreasing energy consumption constraint function, it uses the theoretical results presented by Shabtay & Kaspi and proposes a simulated annealing algorithm. The proposed simulated annealing algorithm can solve the problem consisting of 1000 jobs in 0.1 second and keep the relative error within 0.01%.(4) It researches on the multi-key-machine scheduling problem in which the job release dates and processing times are simultaneously dependent on energy consumption. The purpose of the scheduling is to minimize the total energy consumption under a given makespan. It assumes that the energy consumption constraint function of the job release dates and processing times are linear decreasing. It gives a formal description of the problem and analyses the potential characteristics of the optimal solution. It designs four basic job operations of job left-move, right-move, compression and decompression, discusses the creation of neighborhood with these four operations and calculates the total energy consumption by a modified variable neighborhood search algorithm and simulated annealing algorithm. It also designs a lower bound for the problem to evaluate the accuracy of the solution. Experimental results show that the simulated annealing algorithm can solve the problem effectively.