Complexity and Solution Methods for a Single-Machine Scheduling Problem with Limited Buffer Space and Transportation Resource

In this paper, we study a scheduling problem with one machine, one vehicle and a limited buffer space. This problem is a very simple case of a Flexible Manufacturing System including the aspects of scheduling, of transportation and of blockage since the buffer has a limited space. In this problem, the vehicle must carry jobs, one at a time, from the depot to the machine where the job is laid on the buffer if it is available and then processed by the machine as soon as possible. No preemption is allowed and the job is evacuated from the system once it is processed. The goal is to minimize the completion time of the last job, i.e. the makespan. We provide Mixed Integer Linear Programming and Constraint Programming formulations of the problem and prove its strong NP-hardness. An approximation algorithm with a ratio of 5/4 is also proposed. We construct challenging benchmarks and evaluate the three proposed solution methods.