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

摘要

研究单机带有恶化效应的松弛工期窗口排序问题,其中工件的加工时间是一般的线性恶化。对两类目标函数进行研究:一是提前惩罚、误工惩罚、窗口开始时间以及窗口长度的加权和;二是提前任务数、误工任务数、窗口开始时间以及窗口长度的加权和。目标是确定任务的最优加工顺序、工期窗口开始时间和结束时间使得两类目标函数最小,给出解决此问题的多项式时间算法。