Study On Some Scheduling Problems Under Uncertain Situation

Production scheduling is to plan production process.As a key module,production schedul-ing is the core of advanced manufacturing systems to achieve management technology,logis-tics technology,optimization technology,automation and computer technology development.Optimization techniques and efficient scheduling methods are the basic and key points to re-alize advanced manufacturing and improve production efficiency.Optimizing the production scheduling program can greatly improve production efficiency and resource utilization,and thereby enhance the competitiveness of enterprises.So far,most literature about scheduling problems are focused on deterministic cases.But there are many uncertain variables in the real world,and these variables make the result of a production scheduling deviate from its original goal.If there is enough sample data,statistical methods can be used to obtain the probability distributions when dealing with these uncertain variables.In this case,probability theory is a powerful mathematical tool to study this type of subjective uncertain variables.However,in many cases we do not have enough sample data,then we can only rely on subjective belief degree of experts to deal with such cases.Therefore,it is of great practical significance and theoretical value to study the production scheduling problems with uncertain variables by using the uncertainty theory.In order to deal with subjective belief degrees,uncertainty theory is proposed by Professor Liu Baoding of Tsinghua University in 2007 and become a branch of ax-iomatic mathematics for studying human uncertainty.In this paper,several types of scheduling problems under uncertain situation are studied.The main contributions of this paper are as follows.1.Investigate several kinds of single machine and parallel machine scheduling problems with periodic maintenance.Literature[72]only considered a problem with one unavailable interval.Now,we will consider the problem with more than one unavailable intervals,and then use the longest processing time rule(LPT)or a modified LPT rule-the longest and shortest processing time rule(LSPT)to analyze their worst case ratio.For a single machine scheduling problem,we analyze its worst case ratio by an improved method and get a better result than that in the literature[56].For parallel machines scheduling problems,we use a similar method to get their worst case ratio.Especially for a two-parallel machine scheduling problem,we use LPT to analyze its worst case ratio under uncertain situation.2.Investigate an uncertain single machine scheduling problem with periodic maintenance and establish an uncertain pessimistic value model.Convert the problem into a deterministic problem by the inverse distribution method.Solve the problem by a modified LPT rule mixed with a genetic algorithm.Compare our proposed method with the existing method and numeri-cal examples are given to illustrate the validity of our proposed algorithm.3.Investigate an uncertain flexible flow shop problem subject to breakdowns and convert the problem into a two-stage problem.An uncertain chance constrained model at the first stage and a method to deal with breakdowns at the second stage are proposed.Two intelligent opti-mization algorithms to address the problem are proposed and numerical examples are given to illustrate the validity of the model and algorithms.4.Propose an uncertain chance constrained model for job shop problem with uncertain pro-cessing time and convert the model into a crisp model by the inverse distribution method.Three algorithms are proposed to solve the model,and the three algorithms are compared through some numerical examples.5.Investigate an uncertain two-stage supply chain scheduling problem and propose an uncertain chance constrained model for the first stage.Design corresponding algorithm for each stage of the problem.Illustrate the validity of the model and algorithms via some numerical examples.6.Investigate a single machine scheduling with batch delivery,a integer programming model under deterministic situation is proposed and some domination properties of feasible solution are obtained.Then study the problem under uncertain situation,and establish an un-certain pessimistic value model and get some domination properties of feasible solution.Solve the model by combining uncertain simulation with an intelligent optimization algorithm.Fi-nally,validate the model and algorithm through numerical examples.