单机排序中的一个极小最大绝对迟后问题

摘要

本文考虑n个工件在单机上加工的排序问题,工件j的预期开始加工时间和所需加工时间分别为aj,pj,应交工时间为dj=aj+ kpj+d,这里的k(≥0),d是待定的变量,目标函数为极小化最大绝对迟后。本文首先考虑了该问题一些特殊情况的研究结果,然后在强一致性条件下证得此问题O(nlogn)可解。