工件可拒绝的折衷排序和在线排序

项目名称： 工件可拒绝的折衷排序和在线排序

项目编号： No.11426094

项目类型： 专项基金项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 张利齐

作者单位： 河南农业大学

项目金额： 3万元

中文摘要： 工件可拒绝排序是近年来出现的一种新型排序，它在订货生产系统中有着广泛的应用。近10年来已经吸引了众多国内外研究人员的关注，大量的相关结果也不断涌现。然而，绝大多数文献考虑的目标都是最小化接收工件的加工费用与拒绝工件的拒绝费用之和，并且工件是离线到达或者是按列表在线到达的。本项目主要集中于研究目标为求解所有Pareto最优解的折衷排序，以及工件按时间在线到达的在线排序。为了求解这类问题，需要提出一些新的方法和技巧用以设计一些最优算法、近似算法和在线算法。

中文关键词： 工件可拒绝排序；近似算法；在线算法；NP-困难；动态规划

英文摘要： Scheduling with rejection is a new-type scheduling in recent years which can be widely applied in make-to-order production system. In the last ten years, it has received more and more attentions from many foreign and domestic researchers and a large number of results in this topic were obtained. However, in almost all literature, the objective is to minimize the sum of processing costs of the accepted jobs and rejection penalty of the rejected jobs, and all jobs arrive in the off-line setting or in the on-line over-list setting. In this project, we focus on the trade-off scheduling problems for all Pareto optimal solutions or the on-line over-time scheduling problems. To solve these problems, we must provide some new methods and new skills to design some optimal algorithms, approximation algorithms and on-line algorithms.

英文关键词： scheduling with rejection；approximation algorithm；on-line algorithm；NP-hard；dynamic programming