Research On Intelligent Scheduling Optimization Methods In The Production Process With Piece-Wise Deteriorating Jobs

Scheduling concerns the allocation of limited resources over time to perform a collection of different tasks while satisfying specific requirements and constraints. It exists widely in various types of manufacturing systems. Production scheduling is one of the key decision making processes in manufacturing system. Its optimization analysis is the main research content of production management. The optimization of production schedule is an important means of improving production efficiency. In the classical model of scheduling theory, it is assumed that the processing times of all jobs are known in advance and remain constant during the entire process. However, this assumption may not be applicable to model some practical situations, where the processing time of these jobs depend on their starting times or their position in the sequence. Such kinds of jobs are called deteriorating jobs. If some jobs fail to be processed prior to a pre-specified threshold, their processing times will be extended by adding the extra penalties. This type of deterioration may be presented by a piecewise linear function or a stepwise function. This new classes of scheduling problems with the piecewise deteriorating effect are more complex than the classical scheduling problems, most of which are NP-hard. It is impossible to obtain the optimal solution in the reasonable computational time for these intractable problems. How to solve these scheduling problems has both theoretical and practical aspects.In this dissertation, single machine scheduling problem with piecewise linear deteriorating jobs is considered in detail firstly. Subsequently, three types of scheduling problems with step-wise deteriorating jobs are studied. Since these problems are NP-hard, it is difficult to design a polynomial time algorithm. Some efficient heuristics or meta-heuristics are proposed to obtain the near-optimal schedule in this study. The main contributions of this dissertation are listed below.(1)The single machine scheduling problem with piecewise linear deteriorating jobs is studied for minimizing the makespan. Since the problem is NP-hard in the strong sense, there is no polynomial time algorithm to find the optimal schedule. To solve the problem, a heuristic named DSPT-PI based on SPT rule is proposed to find the near-optimal solution. In addition, an improved genetic algorithm is designed for improving the quality of the solution. An initial individual is generated by DSPT and other individuals are initialized with random job permutations. A linear order crossover operator and a mutation operator based on the sequencing property of problem are used in the algorithm. To speed up the convergence of the algorithm, a local search strategy based on the pairwise interchanging is adopted. Extensive numerical experiments are carried out randomly generated test instances for evaluating the performance of the proposed algorithms. The heuristic DSPT-PI significantly outperforms the existed heuristic and the solutions delivered by the proposed genetic algorithm is better than that given by simulated annealing algorithm.(2) For single machine scheduling problem with stepwise deteriorating jobs, two objective functions, i.e. the total tardiness and the total weighted tardiness, are considered. For the considered problems, the mixed integer programming models is formulated. The total tardiness problem is proved to be NP-hardness, and a heuristic named IMDD based on the modified due date rule and a simple weighted search procedure are designed to solver the problem. Moreover, the weighted tardiness problem is proved to be NP-hardness in the strong sense, and a general variable neighborhood search (GVNS) algorithm is proposed to obtain the near optimal schedule. Computational experiments based on randomly generated instances are showed the GVNS is efficient in solving the problem under consideration. In particular, the average relative percent deviation obtained by GVNS for the large-sized instances is only 0.78% and the corresponding relative average deviation is 0.81%.(3) The parallel machine scheduling problem with stepwise deteriorating jobs is considered for minimizing the total completion time. The different mixed integer programming models are proposed based on different decision variables for analyzing the efficiency of various models. A weight-combination search algorithm that is used to solve single machine scheduling problem is modified for solving the studied problem. Let MWCSA denote the modified heuristic. Meanwhile, a variable neighborhood search (VNS) based on job permutation encoding scheme is also proposed. In order to speed up the search of VNS, the heuristic MWCSA is used to produce the initial solution of VNS. The obtained improved algorithm is called VNS+MWCSA. Since the deteriorating dates can be picked up from different intervals, it generates three types of instances. Experimental results show the efficiency of the mixed integer programming models depends on the deteriorating intervals and the VNS+MWCSA algorithm outperforms the other methods.(4) For minimizing the total tardiness, the parallel machine scheduling problem with stepwise deteriorating jobs and setup times is considered. The mixed integer programming model is presented. For this problem, a hybrid discrete cuckoo search algorithm is proposed. The single sequence of all jobs is encoded for the solutions in the algorithm. In order to generate a good initial swarm, a modified heuristic named the MBHG is incorporated into the initialization of population. Several discrete operators are used in the random walk of Levy Flight and the crossover operation. Moreover, a local search procedure based on variable neighborhood descent is integrated into the algorithm as a hybrid strategy in order to improve the quality of elite solutions. In order to maintain the diversity of the population, the partial solutions adopt a restarting mechanism at the searching process. Experimental results show that the proposed hybrid algorithm can yield better solutions in comparison with the other algorithms, and its efficiency is affected by the distribution of deteriorating date slightly.This disseration studies single machine and identical parallel machine scheduling problems under production process with piecewise deteriorating jobs. In the four problems under consideration, three objective functions, i.e. the makespan, the total tardiness and the total completion time, are considered. This study enrichs the research content of the scheduling problem with piecewise deteriorating jobs, which is helpful to push the development of production scheduling theory, widens the solution approach of these problems and has great significance in theory and application.