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

A Single Machine Maximal Absolute Lateness Scheduling Problem

作　　者：罗润梓[1] 孙世杰[1] 

机构地区：[1]上海大学数学系,上海200436

出　　处：《应用数学与计算数学学报》2001年第1期1-9,共9页Communication on Applied Mathematics and Computation

基　　金：国家自然科学基金资助项目(项目编号为 19771057).

摘　　要：本文考虑n个工件在单机上加工的排序问题,工件j的预期开始加工时间和所需加工时间分别为aj,pj,应交工时间为dj=aj+ kpj+d,这里的k(≥0),d是待定的变量,目标函数为极小化最大绝对迟后。本文首先考虑了该问题一些特殊情况的研究结果,然后在强一致性条件下证得此问题O(nlogn)可解。In this paper, we study the problem of scheduling n jobs on a single machine. Eachjob j has a target starting processing time aj, a processing time pj while its due datedj = aj + kpj + d has to be decided by k and d where k(≥0) and d are decision variableswhich we need to determine. The objective is to minimize the maximum absolute lateness.In this paper we discuss certain results of this question under some special conditions first, wethen show it is solvable by a graphical approach in O(nlog n) time under strong uniformnesscondition.

关 键 词：单机排序 绝对迟后 强一致性条件 目标函数 极小化 最优加工顺序 

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