The Discrete Resource Allocation Problem in Flow Lines
研究确定性流水线中离散资源分配问题，假设加工时间随资源增加而凸性递减，针对固定作业序列的不同绩效指标建立凸规划模型，证明问题强NP完全，并提出隐枚举求解方法。
In this paper we address the discrete resource allocation problem in a deterministic flow line. We assume that the processing times are convex and nonincreasing in the amount of resources allocated to the machines. We consider the resource allocation problem for a fixed sequence of jobs for various performance criteria (makespan, weighted sum of completion times, cycle time for cyclic schedules), and develop a formulation of the problem as a convex program, where the number of constraints grows exponentially with the number of jobs and machines. We also present a generalization of the formulation for resource allocation problems in acyclic directed graphs. We demonstrate that the problem is NP-complete in the strong sense and present an effective solution procedure. The solution procedure is an implicit enumeration scheme where a surrogate relaxation of the formulation is used to generate upper and lower bounds on the optimal objective function value. Finally, we address the simultaneous scheduling and resource allocation problem, and we present an approximate and iterative solution procedure for the problem.