Minimising total earliness and tardiness with periodically supplied non-renewable resource profiles
研究一类特殊资源约束的单机调度问题，其中非可再生资源在计划周期的不同时期供应，目标是最小化总提前与总延误之和，并提出了一个可扩展的算法。
We consider a special class of resource-constrained single machine scheduling problems. In the classical scheduling context, resource types are classified into renewable and non-renewable; however, a large variety of real-world problems may not fit into one of these classes, e.g. labour regulations in project scheduling, budget allocation to different phases of a construction project, and dose management in a medical imaging centre. In this study, we address a class of non-renewable resources supplied, not necessarily immediately, in different periods of the planning horizon. The objective is to assign the jobs to the supply periods and schedule them such that the sum of total tardiness and total earliness is minimised. Several properties and complexity results of the optimal schedules are discussed, then they are used to develop a tractable algorithm. First, we decompose the problem into several single supply problems and then decide the optimal schedule through a polynomial-time optimal algorithm for each single supply problem. The scalability tests indicate the promising performance guarantee of the algorithm compared to provably optimal schedules in the integrated framework.