Single-Machine Scheduling to Minimize the Size of Input Buffer

This paper investigates a single-machine scheduling problem with a finite-capacity input buffer. In this problem, each job is assigned to the machine at its release date and started immediately or sent to the input buffer to wait for processing. The problem in this study is to find a schedule that minimizes the required size of the input buffer. Its strong NP-hardness will be shown first, and next, a pseudo-polynomial time dynamic program will be developed for another ordinary NP-hard case. Three mixed integer linear programming models are presented using different formulation approaches. We also design four heuristic algorithms to produce approximate solutions in a reasonable time. Numerical experiments appraise the effectiveness of the formulations.