首页 | 官方网站   微博 | 高级检索  
     

一个具有两类工件的多目标排序的NP-困难性
引用本文:冯琪,原晋江.一个具有两类工件的多目标排序的NP-困难性[J].运筹学学报,2007,11(4):121-126.
作者姓名:冯琪  原晋江
作者单位:1. 中原工学院理学院,郑州,450007
2. 郑州大学数学系,郑州,450052
摘    要:文章考虑具有两个工件集的单机排序问题.第一个工件集J1以加权完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小,并证明该问题是强NP-困难的.

关 键 词:运筹学  排序  多目标  计算复杂性  NP-困难的
收稿时间:2006-10-17
修稿时间:2006年10月17

NP-hardness of a Multicriteria Scheduling on Two Families of Jobs
Feng Qi,Yuan Jinjiang.NP-hardness of a Multicriteria Scheduling on Two Families of Jobs[J].OR Transactions,2007,11(4):121-126.
Authors:Feng Qi  Yuan Jinjiang
Abstract:This paper consider a single-machine scheduling problem having two families of jobs. The first family J1 has the total weighted completion time as its objective function, and the second family J2 has the maximum weighted completion time as its objective function. The goal of the problem is to seek for a schedule such that the total weighted objective function of two criteria is minimized, and shows that the problem is strongly NP-hard.
Keywords:Operations research  scheduling  multicriteria  computational complexity  NP-hard
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号