带有准备时间和凸资源分配的单机排序问题  

Single-Machine Scheduling Problem with Due-Window Assignment and Setup under Convex Resource Allocation

作　　者：李石 LI Shi(School of Mathematics and System Science,Shenyang Normal University,Shenyang,Liaoning 110034,China)

机构地区：[1]沈阳师范大学数学与系统科学学院,辽宁沈阳110034

出　　处：《平顶山学院学报》2018年第5期17-23,共7页Journal of Pingdingshan University

基　　金：国家自然科学基金(11171050);辽宁省教育厅科学研究一般项目(L2014433)

摘　　要：讨论带有凸资源分配和准备时间且具有交货期窗口的单机排序问题.在凸资源消费函数条件下研究目标函数,所有工件有一个公共交货期窗口,工件的实际加工时间具有退化效应并依赖于分配给工件的负荷量以及不可再生资源数量,同时依赖于工件的开始加工时间.每个工件还有一个可控的准备时间,同样依赖于所分配的不可再生资源数量.目标是在资源总量有限的前提条件下,确定工件最优排序、资源分配、交货期窗口位置,极小化带有提前、延误、公共交货期窗口开始时间、交货期窗口大小的总费用.将上述问题转化为匹配问题,并给出一个启发式算法.This paper studies a single machine scheduling problem with due -window assignment and setup under convex resource allocation. The actual processing time of a job is a convex function of the resource amount allocated to it. All jobs have a common due -window. The actual processing time of each job has deteriorating effect and depends on the workload of the job, its allocation of non - renewable resource and its starting time. Each job also has a setup time which depends on its allocation of non - renewable resource. The objective is to minimize the weighted costs of earliness, tardiness, the starting time of the common due - window, the size of the due - window by determining the optimal sequence and the optimal resource allocation under the premise that the total resources are limited. We present a heuristic algorithm to solve the problem by transforming it into matching problem.

关 键 词：排序 资源分配 退化效应 准备时间 匹配问题 交货期窗口 

分 类 号：O223[理学—运筹学与控制论]