Scheduling on a Single Machine and Parallel Machines with Batch Deliveries and Potential Disruption

Abstract EN

In this paper, we study several coordinated production-delivery scheduling problems with potential disruption motivated by a supply chain in the manufacturing industry.

Both single-machine environment and identical parallel-machine environment are considered in the production part.

The jobs finished on the machines are delivered to the same customer in batches.

Each delivery batch has a capacity and incurs a delivery cost.

There is a situation that a possible disruption in the production part may occur at some particular time and will last for a period of time with a probability.

We consider both resumable case and nonresumable case where a job does not need (needs) to restart if it is disrupted for a resumable (nonresumable) case.

The objective is to find a coordinated schedule of production and delivery that minimizes the expected total flow times plus the delivery costs.

We first present some properties and analyze the NP-hard complexity for four various problems.

For the corresponding single-machine and parallel-machine scheduling problems, pseudo-polynomial-time algorithms and fully polynomial-time approximation schemes (FPTASs) are presented in this paper, respectively.