带有恶化效应的松弛工期窗口排序问题  

Slack due window assignment scheduling with deterioration effects

作　　者：黄雪 骆思雯 王吉波 HUANG Xue;LUO Si-wen;WANG Ji-bo(College of Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学理学院,沈阳110136

出　　处：《沈阳航空航天大学学报》2022年第1期85-90,共6页Journal of Shenyang Aerospace University

基　　金：国家自然科学基金(项目编号:71471120);辽宁省自然科学基金(项目编号:2020-MS-233);辽宁省“兴辽英才计划”(项目编号:XLYC2002017)。

摘　　要：研究单机带有恶化效应的松弛工期窗口排序问题,其中工件的加工时间是一般的线性恶化。对两类目标函数进行研究:一是提前惩罚、误工惩罚、窗口开始时间以及窗口长度的加权和;二是提前任务数、误工任务数、窗口开始时间以及窗口长度的加权和。目标是确定任务的最优加工顺序、工期窗口开始时间和结束时间使得两类目标函数最小,给出解决此问题的多项式时间算法。This paper studied the single-machine scheduling problem of slack due-window assignment with deterioration effect,where the processing time of the job had a general linear deterioration.Two kinds of objective functions were studied,one was the weighted sum of earliness and tardiness,the start time of window and the length of window,the other was the weighted sum of the number of tasks in earliness and tardiness,the start time of window and the length of window.The goal was to determine the optimal processing order of the jobs,the start time and the end time of the due window to minimize the two objective functions.The polynomial time algorithm was given to solve this problem.

关 键 词：单机 恶化效应 松弛工期窗口 排序问题 多项式时间算法 

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