Single‐Machine Scheduling to Minimize the Size of Input Buffer
研究单机调度中如何安排作业顺序以最小化输入缓冲区容量，证明问题强NP难，提出动态规划、混合整数线性规划模型和启发式算法，并通过数值实验评估效果。
ABSTRACT 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.