具有凸资源约束的单机指数学习效应问题

研究在所有工件的正常加工时间均相同的情况下具有指数学习效应和凸资源约束的单机排序问题.给出了两种模型:在资源消耗总费用有限的情况下,以工件的最大完工时间为目标函数;在工件的最大完工时间有限的情况下,以资源消耗总费用为目标函数.求两种模型下的最优排序和最优资源分配,使得目标函数最小.证明这两个问题都是多项式时间可解的,并给出了相应的算法.

Single Machine Exponential Learning Effect Problems with Convex Resource Constraint

In this paper,we consider single machine scheduling with exponential learning effect and convex resource constraint,where the normal processing times of all jobs are identical.For two scheduling models:to minimize the makespan subject to total resource consumption cost is limited;to minimize the total resource consumption cost subject to the makespan is limited.The goal is to determine the optimal schedule and the resource allocation such as the objective cost is minimized.We prove that these two problems can be solved in polynomial time respectively,and we also provide the polynomial time algorithms to solve these two problems.