工件带简单线性恶化函数和共同交货期单机排序问题  

Scheduling Simple Linear Deteriorating Jobs On a Single Machine with Common Due Date

作　　者：余英[1] 舒彤[2] 曾春花[1] 

机构地区：[1]凯里学院数学科学学院,贵州凯里556011 [2]湖南大学工商管理学院,湖南长沙410000

出　　处：《运筹与管理》2016年第1期154-157,共4页Operations Research and Management Science

基　　金：国家自然科学基金项目(71172194);贵州省科技厅与凯里学院2014年度省校合作协议项目:(黔科合LH字[2014]7232);贵州凯里学院院级课题自科类重点课题(Z1402);贵州省科技厅;黔东南州科技局;凯里学院科技联合基金(黔科合字LKK[2013]30号)

摘　　要：本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。A single machine scheduling problem with simple linear deterioration processing time is studied. The due date times of all jobs are assumed to be common simultaneously. Our aim is to find an optimal sequence so as to minimize the total of the earliness award and tardiness penalty. A pseudo-polynomial time solvable dynamic algorithm is addressed to it under inverse agreeable ratio condition. We also propose a fully polynomial time solv- able approximation scheme（FPTAS） to that problem by geometric rounding technique.

关 键 词：单机排序 动态规划算法 近似算法(FPTAS) 几何舍入技巧 

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