机构地区: 沈阳师范大学数学与系统科学学院,沈阳110034
出 处: 《沈阳师范大学学报(自然科学版)》 2017年第3期305-310,共6页
摘 要: 讨论具有截断控制参数学习效应和退化效应且工件的加工时间依赖于资源分配的单机排序问题。分别在线性资源和凸资源消费函数条件下研究问题。每个任务有一个松弛工期窗口,任务的实际加工时间依赖于截断控制参数、工件的开始加工时间和分配方案的资源数量。目标是求出任务的最优排序、每个任务的工期窗口位置、最优资源分配,使由任务总提前、延误、工期窗口的开始时间、窗口大小、时间表长、总完工时间及资源总费用的加权和最小。将问题转化为指派问题,证明了该问题是在多项式时间内可解的,并分别给出了2个多项式时间的最优算法。 In this paper,we study a single machine scheduling problem with truncated job-dependent learning effect and deterioration effects and processing time dependent on resource. Each job has a slack due-window. The actual processing time of a job is a linear function and a convex function of the resource amount allocated to it,respectively. The actual processing time of each job depends on a truncated control parameter,the starting time and the resource amount allocated to it. The objective is to find the optimal sequence of jobs,slack due-window and the optimal resource allocation scheme to minimize the weighted costs of earliness,tardiness,the starting of due-window,and the size of the due windows,makespan,the total completion times and the resource allocation. We show that the problem is polynomial solvable by transforming this it into an assignment problem. Two polynomial time optimal algorithms are presented,respectively.