Algorithm Research For Some Stochastic Scheduling Problems

In this paper, we first mainly study the scheduling problem with incomplete and uncertain information, i.e. stochastic online problem. For the non-preemptive and pre-emptive settings, we study the problems on single machine, identical parallel machines and uniform machines. Several approximation policies are introduced for those prob-lems. Then we consider problem with random machine breakdowns and stochastic E-T problem. The layout of the dissertation is as follows.In Chapter one, we first introduce basic concepts of scheduling problem, then we discuss the stochastic online problem including the online information and stochastic in-formation. We also give some methods to analyze the competitive value of approximation policies. Finally, we introduce the problem model with random machine breakdowns and stochastic E-T problem model.In Chapter two, we consider the non-preemptive stochastic online scheduling, and the objective is to minimize the expected value of total weighted completion times. (1) For single machine scheduling, inspired by the algorithm for deterministic online problem in [25], we respectively introduce deterministic and randomized policies with the competitive value 2+δand 2. For the problem on m uniform machines, by the concept of piece of work in [20], we prove the asymptotical optimality of D-WSEPT policy when the processing times and weights are uniformly bounded. For the related work, Chou et al.proved the convergence in expectation of policy WSEPT for single machine, flow shop and open shop problems. Chen et al.considered the problem on m uniform machines. With some assumptions on processing times, weights and arriving dates, they concluded that objective value obtained by any nondelay policy converges to optimal value by probability one.In Chapter three, we study the preemptive stochastic online problem, and the objec-tive is to minimize expected value of total weighted completion times. For the problem, Megow et al.respectively considered the problems on single machine and on m identi-cal parallel machines, and gave two polices with common competitive of 2. In [113], For the offline problem on single machine where all jobs have a common arriving date and job's weight may change during processing, Weiss gave an optimal policy. We consider the combination of the settings above. (1) For the online problem on single machine, when job's weight is only allowed to increase during its processing, we give an 2+δ-approximation policy. (2) For problem on m identical machines, we consider weight's increasing and decreasing environments and respectively give approximation polices with competitive values and 2. (3) For the problem on two uniform machines where the job weight is only allowed to decrease, we also give a 2-approximation policy.In Chapter four, we research three stochastic E-T problems. (1) processing times of all jobs are equal to a constant, but different jobs could have different weights. The common due date is a random variable. We denote the problem as 1|pj= p,d-stoch|E(Σwj(Ej+Tj))。For the two cases where the due date follows general discrete distribution and continuous distribution, we respectively develop a pseudo-polynomial al-gorithm and a polynomial algorithm. (2) The processing times and the common due date are constants, but a machine breakdown may happen. The uptime is a given parameter while the downtime is a random variable. For the problem we devise a pseudo-polynomial dynamic programming algorithm, and the overall complexity is O(nr2TPn) where r is the time when breakdown occurs and TPn denotes the total processing times. (3)The processing times are subject to independent distributions, preemption is allowed and the common due date follows exponential distribution. With the objective to minimize E(Σ(αjEj+βjUj)), we introduce an optimal policy Pre-OPT.In Chapter five, we consider the stochastic scheduling with random breakdowns on single machine and the objective is to minimize the expected makespan. Assume jobs' processing times are constants and arriving dates are zero. The uptimes are random vari-ables subject to independent and identical distribution. Besides, we assume the machine breakdowns are independent with the job processing on it. For the problem, Kasap et al.achieved some conclusions in 2006, but the authors pointed out that the proof is not correct in [58]. In this dissertation, we consider a special case where the uptimes are subject to common uniform distribution independently, and we prove that the LPT policy is optimal.