CSpace  > 应用数学研究所
Xu Yangyang; Cui Jinchuan
Source Publicationactamathematicaeapplicataesinica
AbstractWe 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.
Funding Project[Daqing oilfield company Project of PetroCHINA] ; [Key Laboratory of Management, Decision and Information Systems, Chinese Academy of Sciences] ; [Beijing Research Center of Urban System Engineering]
Document Type期刊论文
Recommended Citation
GB/T 7714
Xu Yangyang,Cui Jinchuan. avariantofmultitasknvehicleexplorationproblemmaximizingeveryprocessorsaverageprofit[J]. actamathematicaeapplicataesinica,2012,28(3):463.
APA Xu Yangyang,&Cui Jinchuan.(2012).avariantofmultitasknvehicleexplorationproblemmaximizingeveryprocessorsaverageprofit.actamathematicaeapplicataesinica,28(3),463.
MLA Xu Yangyang,et al."avariantofmultitasknvehicleexplorationproblemmaximizingeveryprocessorsaverageprofit".actamathematicaeapplicataesinica 28.3(2012):463.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Xu Yangyang]'s Articles
[Cui Jinchuan]'s Articles
Baidu academic
Similar articles in Baidu academic
[Xu Yangyang]'s Articles
[Cui Jinchuan]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Xu Yangyang]'s Articles
[Cui Jinchuan]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.