Scheduling With Release Times On A Single Semicontinuous Batch Processing Machine

The problem of semicontinuous batch processing machine arised in theheating-process of the furnace in the iron and steel industry. The principal characterof this problem is that, jobs processed in batch. That means job in the same batchmust enter and leave machine continuously, namely, the new batch will not startprocessing until every job in the former batch completed processeing. Theprocessing time of jobs in the same batch is the longest processing time of jobs in thebatch. The capacity of batch is infinite because the jobs in the same batch enter andleave machine continuously. Because of the release time, there are two cases in theprocessing procedure for one batch: existing places or no empty place. In this paper,we consider both of the two cases mentioned above. The main content of this paperincludes as following:1. In the processing procedure, if there is no empty place between the jobs of thesame batch, namely, the jobs enter or leave the machine one after another in a period.This paper mainly makes a discussion from two aspects.(1) The purpose is to improve the utilization ratio of the machine. Namely, weconsider a scheduling problem which the objective function is the makespan. If thejob release times and processing time are agreeable, we analysis the properties of theoptimal solution and a dynamic programming algorithm which the computationalcomplexity of O (n2) is proposed. The optimality of the algorithm is proved, and anumerical example properties is given to explain the algorithm.(2) Due to the problem which the processing time of weighted jobs is equal, theproperties of optimal solution of scheduling problem, which the objective function isthe makespan, are given. When the job of release times and weight are disagreeable,in order to reduce the working-in-processing inventories, we consider the objectivefunction is the weighting total completion time. We analysis of the optimal solutionproperties and provide a heuristic algorithm. Finnal, a numerical example illustrates the heuristic algorithm.2. We also discuss the case that ther are some empty places between the jobs ofsame batch in the processing procedure. In that case, the machine and the jobs areavailable. If the release times of the job and the processing time are agreeable, theobjective function is the makespan, we analysis the properties of the optimal solutionand provide a heuristic algorithm. A numerical example is given to explain thealgorithm.