A Variant of Multi-task n-vehicle Exploration Problem: Maximizing Every Processor's Average Profit  

作　　者：Yang-yang XU Jin-chuan CUI 

机构地区：[1]Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China

出　　处：《Acta Mathematicae Applicatae Sinica》2012年第3期463-474,共12页应用数学学报（英文版）

基　　金：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.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 

分 类 号：TP332[自动化与计算机技术—计算机系统结构] TN41[自动化与计算机技术—计算机科学与技术]