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 等数据库收录! |