Research On Optimizing Algorithms Of Scheduling Problems For Just-In-Time

The scheduling problems are originating from industrial manufacturing field,are now widely applied in many fields such as industrial production,operation management and logistics.Scheduling problems are one of the important combinatorial optimization problems,which can be described as determining optimal scheduling sequence of tasks(or jobs)to minimize the objective function under certain conditions.In related fields,efficient sequence can improve processing efficiency,save and reduce the consumption of resources,shorten the implementation time,and obtain greater benefits.Just-in-time(JIT)emphasizes that both earliness and tardiness have a great impact on the results.The scheduling problems for JIT with learning effect and(or)deterioration effect and(or)resource allocation need to be studied further.In this dissertation,the scheduling problems on JIT objective function with learning effect and(or)deterioration effect and(or)resource allocation are studied,and some algorithms to solve the problems are proposed.The main research work and contributions are listed as follows:(1)For the single-machine(or processor)scheduling problems on just-in-time objective function involving position-dependent weight,learning effect and convex resource allocation,this research studies the single-machine scheduling problems with simultaneous considerations of learning effect and resource allocation in the actual processing time,and develops the algorithms for solving the problems.With the common(CON)due date assignment method,the first scheduling problem is that the scheduling cost minimum subject to the total resource consumption cost is restricted to an upper bound,the second scheduling problem is that the total resource consumption cost minimum subject to the scheduling cost is restricted to an upper bound.The scheduling cost is the weighted sum of earliness,tardiness and due-date cost,and the weight is a position-dependent weight.For the two problems,the properties of the optimal solutions are given,and the related lemmas are presented and proved,and corresponding solution algorithms and time complexity analysis of the algorithms are proposed.(2)For the single-machine CON due date assignment scheduling problems on just-in-time objective function involving position-dependent weight,deterioration effect,convex(or linear)resource allocation,this research studies the single-machine scheduling problems with simultaneous considerations of deterioration effect and resource allocation in the actual processing time,and develops the algorithms for solving the problems.With the convex resource consumption model,the analyses are given for the three combinatorial problems of the scheduling cost and total resource consumption cost,and it is proved that these problems can be solved in polynomial time respectively,and corresponding solution algorithms are proposed.With the linear resource consumption model,the analyses are done for the linear combinatorial of the scheduling cost and total resource consumption cost minimization,corresponding solution algorithm is proposed,and it is proved that this problem can be solved in polynomial time.(3)For the single-machine scheduling problem on just-in-time objective function involving position-dependent weight,learning effect and deterioration effect,this research studies the single-machine scheduling problem with learning effect and deterioration effect,and develops the algorithm for solving the problem.The objective function is the weighted sum of earliness,tardiness and due-date cost.With the common(CON)due date assignment method,the weight is a position-dependent weight.The objective function is minimized,corresponding solution algorithm is proposed.It is proved that the scheduling problem can be solved in polynomial time.(4)For the two-machine(or processor)no-wait flow shop scheduling problems on just-in-time objective function involving position-dependent weight,learning effect and convex resource allocation,this research studies the two-machine no-wait flow shop scheduling problems and develops the algorithms for solving the problems.The no-wait flow shop is that the job is processed on the second machine without stopping(no-wait)after the job is processed on the first machine.Under job actual processing time with simultaneous considerations of learning effect and resource allocation,the three combinatorial problems of the scheduling cost and total resource consumption cost are studied,i.e.,the sum of the scheduling cost and total resource consumption cost minimization,the scheduling cost minimum subject to the total resource consumption cost is restricted to an upper bound,the total resource consumption cost minimum subject to the scheduling cost is restricted to an upper bound.For these three problems,the properties of the optimal solutions are given,and corresponding solution algorithms and time complexity analyses of the algorithms are proposed.In summary,the main work of this dissertation focuses on the scheduling problems on JIT for position-dependent weight with learning effect and(or)deterioration effect and(or)resource allocation,and the algorithms for solving the problems.Each problem is analyzed in detail,the lemmas are given and proved,and the algorithms are proposed for solving the problems.Experiments on the scheduling problems of this dissertation show that the proposed algorithms can solve the problems in acceptable time,which verifies the feasibility and accuracy of the algorithms.The research achievements of this dissertation will provide reference and support for scheduling problems including learning effect,deterioration effect,resource allocation and just-in-time objective function,for the algorithms to solve the scheduling problems.