运筹与管理2016，Vol.25Issue(1)：154-157,4.DOI:10.12005/orms.2016.0020
工件带简单线性恶化函数和共同交货期单机排序问题
Scheduling Simple Linear Deteriorating Jobs On a Single Machine with Common Due Date
摘要
Abstract
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)/几何舍入技巧Key words
single machine scheduling/dynamic algorithm/approximation scheme/geometric rounding technique分类
数理科学引用本文复制引用
余英,舒彤,曾春花..工件带简单线性恶化函数和共同交货期单机排序问题[J].运筹与管理,2016,25(1):154-157,4.基金项目
国家自然科学基金项目（71172194）；贵州省科技厅与凯里学院2014年度省校合作协议项目（黔科合LH字［2014］7232）；贵州凯里学院院级课题自科类重点课题（Z1402）；贵州省科技厅、黔东南州科技局、凯里学院科技联合基金 （）
