Rescheduling For The Batching Machine

Scheduling is an important branch of the combinatorial optimization, its widelyapplication background has attracted numerous experts and scholars. Scheduling is to assignsome jobs under certain constrains and gives a processing order, so as to make our objectivefunctions attaining the value of optimal. Scheduling can be divided into on-line and off-linescheduling problems. But more and more models of scheduling spring up in recent years. Inthis paper we study a new scheduling model–rescheduling for the batching machine. Thismodel can be described as follows: a set of the original jobs has already been scheduled,which in order to make a given objective function is minimal. When a new set of jobs arrive,the decision maker needs to insert the new jobs into the original schedule without excessivelydisrupting it, so as to make the new objective function to the minimum. The paper isorganized as follows.In chapter1, we briefly introduce some definitions notions and basic information aboutrescheduling and batching machine.In chapter2, we consider rescheduling with the series and the parallel batching tominimize makespan, under a limit on the sequence disruption or the time disruption. Usingthe three-parameter notion convention by Graham et al, these models are described asfollows:(?)In chapter3, we consider rescheduling with the series and the parallel batching to thelateness, under a the limit on the sequence disruption or the time disruption. These models aredescribed as follows:(?)This paper studies on some structure properties of these models and gives the corresponding algorithms, which are proved to be feasible and optimal.