On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost

•We study 10 new supply chain scheduling problems in the on-line environment.•We provide the lower bounds of competitive ratio for all the problems.•We propose optimal algorithms for four of the 10 problems.•We propose approximate algorithms for the other problems.•Computational experiments confirm good performance.

This paper investigates minimization of both the makespan and delivery costs in on-line supply chain scheduling for single-machine and parallel-machine configurations in a transportation system with a single customer. The jobs are released as they arrive, which implies that no information on upcoming jobs, such as the release time, processing time, and quantity, is known beforehand to the scheduler. The jobs are processed on one machine or parallel machines and delivered to the customer. The primary objective of the scheduling is time, which is makespan in this case. The delivery cost, which changes due to the varying number of batches (though the cost for each batch is assumed to be the same) in delivery, is also concerned. The goal of scheduling is thus to minimize both the makespan and the total delivery cost. This scheduling involves deciding when to process jobs, which machine to process jobs, when to deliver jobs, and which batch to include jobs. We define 10 problems in terms of (1) the machine configuration, (2) preemption of job processing, (3) the number of vehicles, and (4) the capacity of vehicles. These problems (P1,P2,…,P10P1,P2,…,P10) have never been studied before in literature. The lower bound for each problem is first proved by constructing a series of intractable instances. Algorithms for these problems, denoted by H1,H2,…,H10,H1,H2,…,H10, respectively, are then designed and a theoretical analysis is performed. The results show that H1, H2, H6, and H7 are optimal ones according to the competitive ratio criterion, while the other algorithms deviate slightly from the optimum. We also design the optimal algorithm for a special case of P5. A case study is provided to illustrate the performance of H5 and to demonstrate the practicality of the algorithms.