On-line Parallel Machine Scheduling With Selective Jobs

Parallel machine scheduling is one of the scheduling models being used extensively. In this paper we consider an on-line parallel machine scheduling problem in which jobs can be chosen. Our model can be represented as:in which D is the time limit of machines, f_j is the profit by processing job J_j. The goal is to select jobs so as to maximize the total profit of all processed jobs during the period that machines can be used.The model we consider in this paper is a new type. It is an on-line scheduling form of the Knapsack Preblem. We have not seen any study on such model elsewhere. Here, online means that jobs arrive over time, and all job characteristics (including arriving times) are unknown before their arrival times. Jobs cannot be scheduled before they arrived. Parallel machine refers to the machine condition in this model which means that there are m machines of the same type and the same working speed. Since the objective of our modelis to be maximized, the worst-case ratio is definited by , for any instance A,σis a sequence obtained by the on-line algorithm,πis an off-line optimal sequence of A. Here, 0≤ρ≤1. Jobs in this model can be chosen. It means that when a job arrives, it can be either accepted to gain profit or rejected to lose profit. Not all the jobs that have arrived must be scheduled on the machines. Rather, all the jobs that have been chosen must begin processing at their arrival times. If a job cannot be processed immediately at its arrival time, it have to be rejected. No job can wait for any time, after its arrival, to be processed. This kind of model is widely applied. For instance, corporations or enterprises purchase some machines with the same type. The arrival times and contents of order forms are unknown before their arrival. When an order form arrives, decisionmaker may accept it or reject it. We are aware that the competition of market is very intense. Order forms accepted must be processed at once. However, those rejected may be accepted by other enterprises, and cannot be accepted alternately in the future. When r_j = 0(j = 1,…,n) and jobs can be processed at some time after its arrival, the off-line problem of this model is in fact a knapsack problem. We can prove that the off-line problem is NP-hard when jobs must be processed or rejected just at its arrival time. In our model, the case that profit f_j and processing time p_j of job J_j have no relevance is very difficult. We consider a special case in this paper: the profit and processing time are linearly dependent. This paper mainly includes two part. In chapter 1, introduction of the theory of scheduling, some fundamental conceptions that we may use, some notation of scheduling and the description of our model. In chapter 2, first, we give an upper bound 1/2 of competitive ratio for the case f_j = 1 and present an instance to show that there is no on-line algorithm which has a constant competitive ratio for the case f-j = p_j. Then, for all the cases, in which jobs' profit and processing time are linearly dependent, f_j =μ_j +λ_jp_j(μ_j,λ_j > 0), there is no on-line algorithm which has a constant competitive ratio. Second, on-line algorithms are presented for the case f_j = 1 and jobs have only two kinds of processing time (small-jobs' processing time is 1 and large- jobs' processing time is d). For the subcase that there are only two machines (m=2) and d≥2, on-line algorithm A~1 has a competitive ratio of at least 1/2 and it is the best possible. For the subcase that m=2k and d≥k+1, on-line algorithm A~2 has a competitive ratio of at least 1/2 and is the best possible. Then for the subcase that m=2k+l and d≥2k + 2, on-line algorithm A2 has a competitive ratio of at least k/(2k+1) and is the asymptotically best possible. Finally, for the case f_j = p_j and jobs have only two kinds of processing time (small-jobs' processing time is 1 and large-jobs' processing time is d), an on-line algorithm A~3 is proposed. For the subcase m=2k and d≥k+1, it has a competitive ratio of at least 1/2 and is the best possible. And for the subcase that m=2k+1 and d≥2k + 2, it has a competitive ratio of at least k/(2k+l) and is the asymptotically best possible.