Categories. Novel Online Batch Scheduling Problem

In this paper, we present and consider some new scheduling problems, which gen-eralize the classic or existing scheduling problems. For classic scheduling problems, thejob's processing time is fxed, and we study the models of single machine scheduling withgeneral processing time functions. There is nearly no article at present about the com-bining models online scheduling and scheduling with deterioration, we considering themand get some new scheduling models. For classic online (over time model) schedulingproblems, the job's information will be known after its release time, i.e., the we shouldmake decision only after job's arrive time. We present a new online model, in which job'sinformation will be known in advance. In this paper the batch scheduling problem meansparallel batch model, the batch machine can process up to B jobs simultaneously as abatch, where B is the capacity of batch machine, the batch processing time is the largestjob processing time in this batch.The paper consists of four parts. In chapter1, we introduce some basic concepts ofscheduling problems and algorithm complexity. A literature review of online scheduling,batch scheduling, and scheduling with deterioration is given.In chapter2, we study the models of single machine scheduling with general process-ing time functions. Two models with general processing time function are considered.Job's processing time is assumed to be basic processing time adds a function of startingtime and position, respectively. For processing over starting time model, the makespanminimization problem and total completion time minimization problem are polynomiallysolvable under certain conditions, which have more generality compared with previousarticles. For processing over position model, there are optimal schedules for makespanminimization problem and total completion time minimization problem. A property ofoptimal schedule and a greedy algorithm for total weighted completion time minimizationproblem are presented.In chapter3, we investigate online scheduling with linear deterioration efect. Jobsarrive over time. The actual processing time pjof Job Jjis assumed to be a linear functionof its starting time t, i.e., pj=bj+αt, where α>0is the deterioration ratio, bjis thebasic processing time, which is unknown until it arrives, the objective is to minimize makespan. For no-batching single machine problem, we prove its lower bound no lessthan For infnite batching single machine problem, an optimal online algorithmβH∞with a competitive ratio of (1+α)β+1is given, where Forinfnite batching m identical machines problem, we provide an online algorithm βmH∞with a competitive ratio ofIn chapter4, we consider a new online model, in which the job's information ar-rive time is online, over time. The time interval between job's information arrive andprocessable time is a, we also know the maximum processing time pmax. Jobs ar-rive over time, the aim is to minimize makespan. For infnite batching single ma-chine problem, we prov(ide the√optimal onl)ine algorithm γH∞with a competitive ratioof1+γ, where γ=1+1+4pmaxpmax+a/2. For infnite batching m identical ma-chines(problem√, an online al)gorithm with a competitive ratio of1+γmis given, whereγm=m+m2+4pmaxpmax+a/2.At last, we make a summary of our paper, and discuss what we can do in the futureresearch.