具有可控和依赖位置负荷处理时间的资源约束单机排序问题

Single Machine Scheduling Problem with Controllable Job Processing Times and Position-Dependent Workloads

摘要: 本文研究具有与任务和位置有关的可控处理时间的凸资源单机排序问题。任务的实际加工时间是所获得的资源量、与任务所在位置有关负荷的函数。考虑两个问题。第一个问题是在资源总量有上界限制条件下，确定任务排序、资源分配方案，使得时间表长最小。第二个问题中资源总量没有限制，目标是求出最小资源总量、任务排序和资源分配方案，使得由时间表长和资源总量加权和取最小值。分别证明了上述问题可以在多项式时间内求出最优解，并给出了求解相应问题的多项式时间最优算法。

Abstract: This paper concerns with a single-machine scheduling problem in which each processing time of jobs is controllable by allocating a continuously nonrenewable resource. We assume each pro-cessing time of jobs has a workload that is both job and position-dependent. Two problems are investigated. In the first problem, the total amount of resource for processing times does not exceed an upper bound. The objective is to determine the job sequence and the resource allocation scheme to minimize makespan; while in the second problem, the total amount of resource is not limited, the aim is to determine the amount of resource used, the job sequence and the resource allocation scheme to minimize a total weighted cost of makespan and resource amount. We show that the problems can be solved in polynomial time and present optimal algorithms, respectively.