松弛工期窗口指派和截断控制学习效应资源约束单机排序问题  

A Single Machine Slack Due-Window Assignment and Scheduling Problem with Truncated Learning Effect and Resource Constraint

作　　者：罗成新 LUO Cheng-xin(College of General Education,Guangdong University of Science and Technology,Dongguan 523073,China)

机构地区：[1]广东科技学院通识教育学院,广东东莞523073

出　　处：《数学的实践与认识》2022年第2期82-89,共8页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11171050);广东科技学院创新强校工程项目(GKY-2019CQYJ-16)。

摘　　要：研究松弛工期窗口指派资源约束单机排序问题,决策者需要在一台处理机上连续处理n个独立的任务.每个任务有一个待定的松弛工期窗口,任务的处理时间通过分配资源可控,且是所在位置的递减函数,当函数递减到一定程度时,需要用一个控制参数替换.目的是在可用资源量有限条件下求出任务的处理顺序和工期窗口以及资源分配方案,使得任务中最大费用取最小值.分两步处理:首先将问题转化为非线性凸规划问题,利用凸规划理论求出任务的资源数量;其次通过解指派问题得到任务最优处理顺序,进而求得任务的工期窗口.给出了多项式时间的最优算法,提供一个算例说明算法的有效性和运算过程.A single machine slack due-window assignment resource constraint and scheduling problem with general truncated job-dependent learning effect is studied.There is a set of independent jobs to be processed on a single machine,each job has a slack due-window to be decided.The processing of a job is decreasing in position.The aim is to find job sequence and due-windows,resource amount allocated to each job that minimizes the maximal cost among all jobs,subject to an upper bound on total resource amount.Firstly,the problem is converted to a nonlinear convex programming problem.By solving it the resource amount allocated to each job is obtained..Secondly,by solving a assignment problem the optimal job seqence is given.Then,the due-windows are obtained.An optimal algorithm in polynomial time is presented.An example is provided to show the efficency of the algorithm.

关 键 词：排序 松弛工期窗口 截断学习效应 最大费用 资源分配 

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