线性减少加工时间的资源约束单机排序问题

Resource constrained single machine scheduling problem with linearly decreasing processing times

讨论具有连续资源的单机排序问题。在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数。考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量。第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间。对两类问题讨论了最优排序的某些特征。基于对问题的分析,分别给出了求解最优资源分配的方法。结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立。

The single machine scheduling problem with continuous resources was discussed. In this model, the release time of a job is a positive strictly decreasing continuous function of the amount of resources consumed, and the processing time of a job is a strictly decreasing linear function of its starting time. Two versions of the problem are addressed. In the first one the objective is to minimize the total resource consumption with makespan constraints, whereas in the second one the objective is to minimize makespan with the total resource consumption constraints. Characterizations of optimal schedules are established for both versions. Based on the analysis of the problems, the optimal resource allocation methods are presented, respectively. The solutions shows that the results of the problems with constant processing times also hold in the case where the processing time of a job is a linear function of its starting time.