Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint

Abstract EN

This paper addresses a parallel-batch scheduling problem that incorporates transportation of raw materials or semifinished products before processing with waiting time constraint.

The orders located at the different suppliers are transported by some vehicles to a manufacturing facility for further processing.

One vehicle can load only one order in one shipment.

Each order arriving at the facility must be processed in the limited waiting time.

The orders are processed in batches on a parallel-batch machine, where a batch contains several orders and the processing time of the batch is the largest processing time of the orders in it.

The goal is to find a schedule to minimize the sum of the total flow time and the production cost.

We prove that the general problem is NP-hard in the strong sense.

We also demonstrate that the problem with equal processing times on the machine is NP-hard.

Furthermore, a dynamic programming algorithm in pseudopolynomial time is provided to prove its ordinarily NP-hardness.

An optimal algorithm in polynomial time is presented to solve a special case with equal processing times and equal transportation times for each order.