Research On Scheduling Algorithm For Production Operating Systems With Learning Effect

In the process of production operation,operators are familiar with machine or process operations constantly,the processing time of the same unit production decreases gradually.This phenomenon is known as the"learning effect".Nowadays,it has become the development trend for society to accelerate upgrading production and increasing customer personalized demand.The learning effect caused by new products,new technologies and new equipments has become particularly prominent issue.Previous researches show that there is a significant difference in the processing time of the same product processed in different positions.In order to increase the accuracy of scheduling,the learning effect is a key factor to be considered in the production operating system.In recent years,the scheduling problem considering the learning effect has gradually become a hot direction in academic research.In this paper,production operating system scheduling problem based on the learning effect is studied.According to the number and relationship of operators and machines,this paper has the following four research focuses:single machine "one-to-one" operating system,multi-machine "one-to-one" operating system,single operator and multi-machine "one-to-many" operating system,multi-operator and multi-machine"one-to-many" operating system.Among them,based on previous researches,the "one-to-one" operating system improves order components and the delivery process of learning effects,while the"one-to-many" operating system considers the impact of the number of operators and the distance between machines on scheduling.This paper focuses on how to achieve efficient scheduling in each system under the learning effect and makes an in-depth analysis of these complex scheduling problems derived from reality.Then,an efficient and available scheduling model is proposed.The effective exact algorithm,heuristic scheduling rules,and intelligent scheduling algorithm are designed.The main research results and innovations are as follows:(1)The single machine "one-to-one" operating system order scheduling problem with learning effect is researched.Firstly,the nonlinear mathematical model for order scheduling is transformed into a mixed integer programming model in which the job is assigned to the order.Then,the problems with two objective functions are discussed including minimizing the total tardiness and minimizing the total weight tardiness,and the exact algorithms are proposed,respectively.To solve the problem minimizing the total tardiness.Split,Decomposition and Elimination rules with learning effect are proposed and proved to be true.Then a branch-and-bound based on Split,Decomposition and Elimination rules with learning effect(BB-SDELE)is developed.The numerical experiment demonstrates that the BB-SDELE is efficient for larger size instance with up to 140 orders,which outperforms all methods of previous researches for similar scheduling problems.When the learning effect is strong and weak,or the due dates are tight and loose,BB-SDELE performs better.To solve the problem minimizing the total weight tardiness,the properties of the problem are analyzed.An improved dynamic programming is designed,and a simulated annealing algorithm(SA)is proposed.The numerical experiment shows that the proposed dynamic programming has a short execution time for solving the small size problems that mean the number of orders is less than 13,and it can get an accurate solution.For large size problems,SA is effective.(2)The multi-machine "one-to-one" operating system order scheduling problem with learning effect is researched,and the mathematical model is established.Two kinds of orders,divisible orders and indivisible orders,are considered separately.To divisible order scheduling problem,the division theorem is present and proved.Therefore,the problem can be transferred into single machine problem according to this theorem,and then the multi-machine scheduling heuristic algorithm based on BB-SDELE is proposed to get an exact solution.To indivisible order scheduling problem,four heuristic algorithms and a hybrid imperialist competitive algorithm with branch-and-bound(ICABB)are presented,in which countries generating,competing,absorbing are improved.The numerical experiment demonstrates that ICABB is effective for this problem comparing to other algorithms,and the multi-machine MDD is fast to solve this problem and performs well.(3)The single operator and multi-machine "one-to-many" operating system scheduling problem with learning effect is researched,the mathematical model has been presented,the single object with minimizing makespan and the multi-object with minimizing makespan and operator walking time are considered respectively.To solve the problem minimizing makespan,the position-based learning effect is considered,and mixed integer programming model is proposed.In order to solve this problem,a greedy operator with learning effect is designed,and two kinds of greedy algorithms with this operator are presented.Then a hybrid simulated annealing algorithm with iterated greedy(SAIG)is proposed,in which the initial solution is improved and two generating new solution methods,multi-job change positions and all job change positions,are proposed.The numerical experiment demonstrates that SAIG is effective for this problem comparing to other algorithms,two generating new solution methods play a great role in improving SAIG.To solve the multi-object problem minimizing makespan and operator walking time,the sum-of-processing-time based learning effect is considered.A hybrid multi-objective genetic algorithm with iterated greedy(MOGA-IG)is proposed,using a multi-objective greedy algorithm with variable greedy bias(MOG-VGB)generating an initial solution set,and mixing fast elitist non-dominated sorting genetic algorithm(NSGA-II)and local search based on the greedy algorithm.The numerical experiment demonstrates that comparing to the diversity of the initial solution set,the quality of extreme solution can improve MOGA-IG more.MOGA-IG is effective for this problem comparing to other algorithms.(4)The multi-operator and multi-machine "one-to-many" operating system scheduling problem with learning effect is researched,a mixed integer programming model is proposed.In order to solve this problem,the meaning of key machine and key job are defined and the method of calculating key index values of machine and job is presented.Multi-operator NEH rule,far and near local search and perturbation methods are improved.Then Key-job based multi-operator iterated greedy algorithm(KMIG)is presented.The numerical experiment demonstrates that KMIG is effective for this problem comparing to other algorithms.Moreover,when the number of operators is small and the distance difference between two machines is large,the optimization space of the problem is larger,and KMIG has a better effect to solve the problem.