Research On Scheduling Of Time-variable Production And Delivery

With the rapid development of information technology, the response of production and delivery is required to be faster and faster. To deal with this requirement, the enterpriser would like to use its resource to make an optimal schedule to make the operation of production and delivery efficiently. In some actual processes, the effect that the production time and the delivery time of a product sometimes changes due to the change of scheduled positions is called as time-variable effect in this paper. Obviously, the change of operation time of a product will make an effect on the decision of the optimal schedule for all the considered products. The research on scheduling with the consideration of time-variable production and delivery are just launched in recent years. Especially, the studies on scheduling with combined consideration of time-variable effect, machine maintenance and group technology are seldom. Motivated by this view, this paper considers scheduling problems with the time-variable effect on the operation time in the process of production and delivery, and also aims to analyze efficient algorithms to solve the considered scheduling problems with the consideration of machine maintenance or group technology.First, severval scheduling problems with machine maintenance are considered. For these studies, this paper considers the single machine scheduling problem with general position-dependent effect and piece-rate maintenance, which depicts the scenario that machine maintenance implement once every a fixed number of jobs completed. The objectives are to minimize the makespan and the total completion time, respectively. Analysis results show that all the studied problems can be optimally solved by polynomial time algorithms. For the general case, the computational complecities of solving algorithms are proved to be O(n4). For the special case that the actual processing time of each job is equal to the product of the normal processing time function of job and the scheduled position function of job, the computational complexities of solving algorithms are proved to be O(n2 log n).At the Second, this paper considers single machine scheduling problem with piece-rate maintenance and two synergetic agents. If the objective functions of these problems are polynomial function, the results show that all the problems without piece-rate maintenance and with two synergetic agents are polynomially solvable; the results also show that all the problems with piece-rate maintenance and two synergetic agents simultaneously are polynomially solvable.At the thrid, this paper considers a single-machine scheduling problem with time-variable effect and periodic maintenance. The objective is to minimize the makespan. The polynomial time approximation algorithms are proposed to solve the problem, the worst ratios, the computational complexities and the performance bounds of the considered polynomial time approximation algorithms are studied. Two hybrid genetic algorithms are also gived to solve the considered problem, and the related numric experiments are proposed to show the efficiency of hybrid genetic algorithms for solving the considered problem.At the fourth, scheduling problems with the consideration of general time-variable effect and group technology are studied. Analysis results show that, even with general position-dependent job processing times, both the single machine makespan minimization group scheduling problems and the parallel-machine total load minimization group scheduling problems can be optimally solved in polynomial time. If the objective is to minimize the makespan, the optimal single-machine schedule for the general case can be obtained by the polynomial solving algorithm whose computational complexity of the solving algorithm is proved to be O(n3); for the special case that the actual processing time of each job is equal to the product of the normal processing time function of job and the scheduled position function of job, the optimal single-machine schedule can be obtained by the Longest Processing Time first (LPT) algorithm whose computational complecities of the solving algorithm is proved to be O(n log n). If the objective is to minimize the total load of all the machines, the optimal parallel machine schedule can be obtained by the polynomial solving algorithm whose computational complexity of the solving algorithm is proved to be O(n3).At the fivth, the integrated production and delivery scheduling problems with single customer under the general aging effects are considered. By analyzing the integrated production and delivery scheduling model under the considered general aging effects, the optimal production schedule under the proposed general aging effects can be obtained by the LPT rule whose computational complexity is O(n log n). Based on the analysis results of the optimal production schedule, both the considered integrated scheduling problems under the summation model and the integrated scheduling problems under the product model can be optimally solved by the LPT rule in O(n log n) time, respectively.At the sixth, the integrated production and delivery scheduling problems with multiple customers under the individual and immediate delivery situation are considered. Based on the conclusions of the production scheduling problems in this paper and the properties of individual and immediate delivery situation, the computational complexities of optimally solving the considered integrated production and delivery scheduling problems with single production machine and multiple customers are proposed. The genetic algorithm with multiple-coding method is adopted to solve an integrated production and delivery scheduling problem with multiple production machines and multiple customers. The computational example of this considered problem is proposed, and its corresponding computational result shows that the genetic algorithm with multiple-coding method can obtain the feasible solution for the considered problem in a reasonable time.In total, for the considered production scheduling problems under time-variable effects or the considered integrated production and delivery scheduling problems under time-variable effects, this paper proposed many results, which are valuable and useful in some actual scheduling processes.