Some Scheduling Problem In Production Management

Scheduling problem is a class of combinatorial optimization, it has an important theoretical significance and wide-ranging background. This thesis mainly conerns two scheduling problems of production management :one is the problem of two parallel machines scheduling with machine disruptions to minimize the weighted number of tardy jobs and the other is an online scheduling problem on a single machine with the job's processing time and delivery time. The thesis is split up into four chapters. We first introduce some preliminary concepts related to scheduling problems and outline the background and significance of the text in chapter1.In chapter2, the problem of two parallel machines scheduling with machine disruptions is discussed. It is assumed that each job is unit-length. Our goal is to minimize the weighted number of tardy jobs. For the case of the transfer time t = 0, an optimal algorithm is presented for the problem P2|D=∞,t=0,p_ij=1|∑w_ijU_ij. Base on this algorithm, an approximation algorithm for the problem P2|D=∞,t≠0,p_ij=1|∑w_ijU_ij is proposed. It is proved that the weighted number of tardy jobs of our algorithm is at most one more than that of the optimal solution.In chapter3, we consider a single-machine on-line scheduling problem with the job's processing time and delivery time. The objective is to minimize the sum time by which all jobs have been completed and delivered. Each job J_j associated with a release time r_j, a processing time p jand a delivery time q jhas to be scheduled on a machine without preemption. It is assumed that the processing times and the delivery times are agreeable, that is, if p_i≥p_j, then q_i≥q_j.We denoted the problem by 1|on-line, r_j , agreeable ( p_j,q_j) |Lmax.An optimal on-line algorithm with the competitive ratio of 2^1/2 is presented. In chapter4, we give the future study and research...