Supply chain scheduling problem in the hospital with periodic working time on a single machine

The warehouse of a hospital is responsible for wrapping medical materials into packages by a baler and dispatching packages to the departments of the hospital periodically to guarantee the requirements of patients. The manager of the warehouse wants to efficiently utilize the wrapping machine and reduce the times of distributions to decrease logistics cost. If we regard the baler as a single machine and medical materials as jobs, the problem can be summarized as a supply chain scheduling problem integrated with production and delivery. Owing to periodic working time of workers, the machine can be viewed as having periodic maintenance. Because the wrapping interruption of medical materials is not allowed in the hospital, processing of any job is nonresumable. All wrapped packages are dispatched before workers are off duty. This means that each delivery batch is delivered just before each maintenance. Our goal is to minimize sum of the total delivery time and the total delivery cost. We show that the problem is strongly NP-hard and provide a -approximation algorithm. Moreover, we propose a branch-and-bound algorithm. Finally we present computational results for some instances generated randomly. Numerical simulation results show that the approximation algorithm performs efficiently.