首页 | 本学科首页   官方微博 | 高级检索  
     检索      

A Variant of Multi-task n-vehicle Exploration Problem: Maximizing Every Processor’s Average Profit
基金项目:Supported by Daqing oilfield company Project of PetroCHINA under Grant (dqc-2010-xdgl-ky-002);Key Laboratory of Management, Decision and Information Systems, Chinese Academy of Sciences;Beijing Research Center of Urban System Engineering
摘    要:We discuss a variant of the multi-task n-vehicle exploration problem. Instead of requiring an optimal permutation of vehicles in every group, the new problem requires all vehicles in a group to arrive at the same destination. Given n tasks with assigned consume-time and profit, it may also be viewed as a maximization of every processor’s average profit. Further, we propose a new kind of partition problem in fractional form and analyze its computational complexity. By regarding fractional partition as a special case, we prove that the average profit maximization problem is NP-hard when the number of processors is fixed and it is strongly NP- hard in general. At last, a pseudo-polynomial time algorithm for the average profit maximization problem and the fractional partition problem is presented, using the idea of the pseudo-polynomial time algorithm for the classical partition problem.

关 键 词:multi-task  n-vehicle  exploration  problem  (MTNVEP)  maximizing  average  profit  (MAP)  fractional  partition  (FP)  NP-complete  strongly  NP-complete

A variant of multi-task n-vehicle exploration problem: Maximizing every processor’s average profit
Authors:Yang-yang Xu  Jin-chuan Cui
Institution:1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China
Abstract:We discuss a variant of the multi-task n-vehicle exploration problem. Instead of requiring an optimal permutation of vehicles in every group, the new problem requires all vehicles in a group to arrive at the same destination. Given n tasks with assigned consume-time and profit, it may also be viewed as a maximization of every processor’s average profit. Further, we propose a new kind of partition problem in fractional form and analyze its computational complexity. By regarding fractional partition as a special case, we prove that the average profit maximization problem is NP-hard when the number of processors is fixed and it is strongly NPhard in general. At last, a pseudo-polynomial time algorithm for the average profit maximization problem and the fractional partition problem is presented, using the idea of the pseudo-polynomial time algorithm for the classical partition problem.
Keywords:multi-task n-vehicle exploration problem (MTNVEP)  maximizing average profit (MAP)  fractional partition (FP)  NP-complete  strongly NP-complete
本文献已被 CNKI 维普 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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