Single-machine Multitasking Scheduling With Job Efficiency Promotion

With the acceleration of economic globalization,the rapid development of Internet technology and the transformation of major social contradictions in China,the operating environment of modern enterprises is undergoing tremendous changes.The shortage of resources,the increasingly fierce competition among enterprises and the more diversified and personalized customer demand have put forward higher requirements for the existing production and manufacturing mode of the enterprise.Facing up with the severe market challenges,enterprises can effectively improve their production,service efficiency or comprehensive deployment capabilities by continuously coordinating their own resources(such as labor and production),time,environment and other factors to formulate strategies in line with the enterprises'production,operation management and scheduling.Only in this way can enterprises make full use of resources to enhance their competitiveness.Scheduling problem is a kind of classical combinatorial optimization problem,which can effectively solve the problem of optimal allocation of resources.Under the complex and variable working environment,the traditional production scheduling model is no longer applicable.Therefore,the concept of multitasking scheduling emerges whose theoretical research and practical promotion play a big role in the production and service process of modern enterprises.In this context,I design a multitasking scheduling model which is more consistent with the actual producing environment and meanwhile solve relevant problems to provide optimization algorithms,which is not only academically significant,but also has a strong practical value.This paper first introduces the research background and significance of the multitasking scheduling problem,and then reviews the literature of the hot issues concerning the scheduling field involved in this paper.Secondly,this paper proposes multitasking scheduling with job efficiency promotion.In the multitasking environment,mutual interference among jobs is inevitable.Therefore,in terms of the classical multitasking scheduling model,the multitasking function consists of two parts:the switching function and the interruption function.Because of the interruption of the primary job which caused by the waiting jobs,the processing time of the primary jobs is consist of the remaining processing time of the primary jobs,the switching time and the processing time of all waiting jobs to be interrupted.This paper first considers the positive effects generated by job switching.Based on the classical multitasking function,a new unified scheduling model is established by introducing a variable efficiency promotion factor which depends on the job and its position.When the efficiency promotion factor is all equal to 1,it returns to the classical multitasking scheduling model.Meanwhile,this paper also proposes a more general DeJong deterioration effect function model related to the jobs itself and its actual processing position.It not only overcomes the disadvantages of the processing time becoming infinite with the infinite backward shift of the position,but also can be considered as a learning effect function model by changing the value of the factor M.Subsequently,considering that the additional resources can affect the job's actual processing time,this paper further combines two different resource allocation models in the new multitasking scheduling model.That is also a major innovation in this paper.In addition,considering that enterprises need to ensure the quality of their products or services while achieving rapid response to market demand,this paper also studies the multitasking scheduling problem with slack due-window based on the production background of just-in-time system.This paper is arranged in a logical way from the shallower to the deeper.Firstly,through the analysis and quantification of the efficiency promotion effect,multitasking scheduling model with job efficiency promotion effect is established.Based on the new model,the three classical scheduling problems are studied,i.e.,the minimization of makespan,the minimization of total completion time and the minimization of total absolute difference in completion times.The paper also provides the corresponding polynomial time algorithm.Secondly,on the basis of the new multitasking model,several single-machine scheduling problems with deterioration effect,resource allocation and slack due-window are discussed respectively and they are proved to be polynomial solvable problems with time complexity O(n ~3).In particular,when any efficiency improvement factor is the same and is not equal to 1,the scheduling algorithm complexity with the slack due-window can be further optimized,and the time complexity will be reached O(nlo g n).Finally,based on the multitasking scheduling model with job efficiency promotion,this paper comprehensively studies the multitasking scheduling problem with slack due-window with both deteriorating effect and resource allocation.In linear and convex resource allocation models,the problem of total cost minimization is discussed including the early completion cost,delayed delivery loss,the opportunity cost of setting the start time of the slack due-window and its size as well as the total resource cost.After stepwise analysis and solution,corresponding optimal algorithms are provided for the two types of resource models.Finally,through designing data example and using LINGO tool,the two most complicated algorithm steps in the fifth chapter of the paper are demonstrated step by step.The validity and feasibility of the proposed algorithm are verified from the practical point of view.