Batch Delivery Scheduling Problems With Unavailability Constraints

In the real industry settings, because of the breakdown or maintenance of themachine during the processing, the machine is unavailable in some interval. In realenvironments, the producers may not stipulate the due date for each specific job;instead, they must have some prespecified dates at which the completed jobs shouldbe delivered. We regard the jobs that are delivered simultaneously as a batch,delivery dates is named batch delivery dates. So the completion time of a batchupon the processing times of all the jobs in the batch, is equal to the sum of theprocessing times of all the jobs in the batch. The completion time of a batch is equalto the completion time of the last job in the batch. All the jobs in a batch have thesame completion time which is equal to the completion time of the batch.Considering unavailability constraints and batch delivery in this paper, the completiontime of a job is not only related to unavailability constraints but also the batchcontaining the job in this model. A batch delivery date is equal to the completiontime of the batch. Hence the flow time of a job is equal to batch delivery date of thebatch containing it. Moreover, for the scheduling problems with generalized batchdelivery dates and earliness penalties, this paper respectively discuss two differentobjective functions when all the jobs have the same processing time. The earlinessof a job is equal to the difference between the delivery time and the completion timeof the job. The specific contents include as follows:1. For the single machine with unavailability constraint at any interval in thecommon case, we discuss the problem that the objective is to minimize the sum of thetotal flow-time and delivery cost. For the above problems, we analysis the propertiesof the optimal solution and give the pseudo-polynomial dynamic programmingalgorithm and the corresponding computational complexity. We show the efficiencyof the algorithm by a specific numeral example.2. For two parallel-machines with unavailability constraint at any interval in thecommon case, we discuss the problem that the objective is to minimize the sum of thetotal flow-time and delivery cost. For the above problems, we provide the propertiesof the optimal solution, pseudo-polynomial dynamic programming algorithm and the corresponding computational complexity.3. For two uniform machines with unavailability constraint in the common case,we also discuss the problem that the objective is to minimize the sum of the totalflow-time and delivery cost. We show the properties of the optimal solution,pseudo-polynomial dynamic programming algorithm.4. For the single machine scheduling problems with generalized batch deliverydates and earliness penalties, the objective is to respectively minimize the sum ofmaximum weighted earliness and weight of the rejective jobs and the sum of weightedearliness and weight of the rejective jobs. For the above problems, we show theproperties of the optimal solution and give the optimal algorithm. Further we verifythe efficiency the algorithm by a numeral example.