Scheduling Problems With Job Cumulative Effects

Scheduling is also called the timetable theory,it is an important part of combinatorial optimization.It is closely to our life,in transportation,smelting,manufacturing and other aspects have a wide range of applications.With the rise of market economy and the im-provement of people's living standard,enterprises need to obtain higher profits with same resources.Scheduling with cumulative effect is a modern model,which is discussed in this thesis.And four chapters are concluded.In Chapter one,we introduce some basic fundamental knowledge of scheduling,algo-rithm,P-problem and NP-problem and some symbols used in this thesis.The cumulative effect model of jobs discussed both in Chapter two and Chapter three is pj(?,r)=pj(1+bj?k=1r-1q?(k))).In Chapter two,we consider the two-uniform-parallel-machine scheduling problem of minimizing the total machine loads.For the NP-hard problem,we present a fully polynomial time approximation scheme with time O(n2/?)by using a half-product function which is an important method in combinatorial optimization.In Chapter three,we address two single-machine scheduling problems of minimizing the makespan,one is the group technology problem,the other is the serial batch problem.For the former,we present an optimal algorithm with time complexity O(mn log n),where m is the number of groups.For the latter,we obtain two polynomial optimal algorithms both for the bounded and unbounded batch capacity c,respectively.In Chapter four,we consider the two-agent scheduling problems on two parallel machines for jobs of cumulative effect pj(?;r)=pj(b+c?k=1r-1 p[k]).Under the restriction of the weighted number of tardy jobs of agent B cannot exceed a given upper bound Q,for problems of minimizing the weighted number of tardy jobs of agent A and the total completion time of agent A,we present two pseudo-polynomial time dynamic programming algorithms,in which some corresponding state variables are considered.