| In recent decades,scheduling has been widely applied in several areas,such as operations research,management science,theoretical computer science and so on.As an important field of scheduling,online scheduling has drawn more and more attention in recent years.Different from off-line scheduling,any information about the future jobs is unknown beforehand in online scheduling.Furthermore,the scheduler must make a chain of decisions by making use of the past events.In some practical cases,however,the partial information of all jobs may be disclosed in advance,which is just semi-online scheduling.In general,the semi-online scheduling is included in the online scheduling.In the traditional scheduling problem,we always assume that all jobs must be accepted and scheduled in a special machine environment to optimize a certain objective value.In most practical cases,nevertheless,owing to the limited production capacity or higher quality requirement,the supplier can only process a subset of all jobs and outsource the remaining jobs to third-party suppliers by paying a certain cost.Note that the outsourcing is just the rejection in this dissertation.There is no doubt that scheduling problems with rejection are very significant both from the perspective of theory and practice.In this dissertation,we focus on the online scheduling problem with rejection on a single machine.In this setting,there are a mountain of jobs being released online over time,which means that,the information of each job Jj,including the release data rj,the processing time pj and the penalty cost ej,is not disclosed upon arrival of this job.Furthermore,each job Jj is either accepted and processed on the machine or rejected by paying a certain penalty cost.It is worth noticing that each job can be rejected at any time after it is released.Furthermore,a machine can only handle an accepted job at the same time.In addition,preemption is not allowed.Our main goal is to minimize the sum of completion times of all accepted jobs plus the sum of penalty costs of all rejected jobs.This dissertation is composed of the following four chapters:In Chapter 1,we briefly introduce the classification and the three-field notation of the scheduling problems.Moreover,we present a brief review of the most related literature which addresses similar problems.In Chapter 2,for ease of presentation,we provide some useful notations,funda-mental definitions and basic lemmas.In Chapter 3,we consider the problem 1|online,rj,(?),rej|∑Cj+R and design a polynomial time semi-online algorithm entitled as ADSPTR.In this chapter,we want to adopt the approach "Improved Instance Reduction" to analyze the competitive ratio.For the purpose of employing the approach "Improved Instance Reduction",we pump some flexibilities into algorithm ADSPTR and introduce a new auxiliary flexible algorithm named as FADSPTR.Note that,ADSPTR is a special case of FADSPTR.Benefiting from the flexibilities of the FADSPTR,the approach "Improved Instance Reduction" can be applied to the algorithm analysis smoothly.By means of the approach"Improved Instance Reduction",we testify that FADSPTR is a semi-online algorithm with a competitive ratio of 1+(?).In Chapter 4,we summarize the results and the contributions of this dissertation,and present some interesting and challenging topics for the future research. |
