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 dest...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.展开更多
Finding the accurate solution for N-vehicle exploration problem is NP-hard in strong sense.In this paper,authors build a linear mixed integer programming model for N-vehicle exploration problem based on its properties...Finding the accurate solution for N-vehicle exploration problem is NP-hard in strong sense.In this paper,authors build a linear mixed integer programming model for N-vehicle exploration problem based on its properties.The model is then proved equivalent to the original problem.Given the model,one can apply the already existed methods and algorithms for mixed integer linear programming on N-vehicle exploration problem,which helps to enrich methods for solving N-vehicle exploration problem.展开更多
The N-vehicle exploration problem(NVEP)is a nonlinear discrete scheduling problem,and the complexity status remains open.To our knowledge,there is no literature until now employing mixed integer linear programming(MIL...The N-vehicle exploration problem(NVEP)is a nonlinear discrete scheduling problem,and the complexity status remains open.To our knowledge,there is no literature until now employing mixed integer linear programming(MILP)technology to solve this problem except for Wang(J Oper Res Soc China 3(4):489–498,2015).However,they did not give numerical experiments since their model existed strictly inequalities and the number of constraints was up to O(n3),which was inefficient to solve practical problems.This paper establishes a more concise MILP model,where the number of constraints is just O(n2).Therefore,the existing efficient MILP algorithms can be used to solve NVEP.Secondly,we provide some properties of N-vehicle problem and give three methods for cutting plane construction,which can increase the solving speed significantly.Finally,a numerical experiment is provided to verify the effectiveness and robustness for different instances and scales of acceleration techniques.展开更多
The research of efficient computation focus on special structures of NP-hard problem instances and request providing reasonable computing cost of instances in polynomial time. Based on the theory of combinatorial opti...The research of efficient computation focus on special structures of NP-hard problem instances and request providing reasonable computing cost of instances in polynomial time. Based on the theory of combinatorial optimization, by studying the clusters partition and the clusters complexity measurement in Nvehicle exploration problem, we build a frame of efficient computation and provide an application of tractability for NP-hard problem. Three N-vehicle examples show that when we use efficient computation mechanism on N-vehicle, through polynomial steps of tractability analysis, decision makers can get the computing cost of searching optimal solution before practical calculation.展开更多
这份报纸扩大单个任务的 n 车辆探索问题到多工 n 车辆探索问题(MTNVEP ) ，由把 n 车辆探索问题与安排问题的工作相结合。起初，作者证明 MTNVEP 为任务的固定数字是 NP 难的，并且它为任务的一般数字是强烈 NP 难的。然后，他们与计...这份报纸扩大单个任务的 n 车辆探索问题到多工 n 车辆探索问题(MTNVEP ) ，由把 n 车辆探索问题与安排问题的工作相结合。起初，作者证明 MTNVEP 为任务的固定数字是 NP 难的，并且它为任务的一般数字是强烈 NP 难的。然后，他们与计算时间 O (n3 n ) 建议一个改进精确算法，它比 O 好(n !) 当 n 变得足够地大。而且，四个启发式的算法被建议。启发式的算法的有效性被实验最后说明。展开更多
Editor’s words The author puts forward some problems involving in CIETAC Arbitration Rules 2000 such as the third nation- ality of the presiding arbitrator, the full autonomy of the parties to choose Arbitration Rule...Editor’s words The author puts forward some problems involving in CIETAC Arbitration Rules 2000 such as the third nation- ality of the presiding arbitrator, the full autonomy of the parties to choose Arbitration Rules and the improvement of applying for interim measures and so on, which are welcomed by CIETAC, though some of which CIETAC does do that in practice, for instance, appointing the third nationalities as presiding arbitrator, and some of which the improvement shall be followed by the law, for instance, the problem of interim measures. We hope there are more articles contributed to arbitration in China directly deal with the theory and practice of arbitration in China as well as all over the world.展开更多
基金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 SciencesBeijing 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.
文摘Finding the accurate solution for N-vehicle exploration problem is NP-hard in strong sense.In this paper,authors build a linear mixed integer programming model for N-vehicle exploration problem based on its properties.The model is then proved equivalent to the original problem.Given the model,one can apply the already existed methods and algorithms for mixed integer linear programming on N-vehicle exploration problem,which helps to enrich methods for solving N-vehicle exploration problem.
基金This work was supported by Key Laboratory of Management,Decision and Information Systems,Chinese Academy of Science.
文摘The N-vehicle exploration problem(NVEP)is a nonlinear discrete scheduling problem,and the complexity status remains open.To our knowledge,there is no literature until now employing mixed integer linear programming(MILP)technology to solve this problem except for Wang(J Oper Res Soc China 3(4):489–498,2015).However,they did not give numerical experiments since their model existed strictly inequalities and the number of constraints was up to O(n3),which was inefficient to solve practical problems.This paper establishes a more concise MILP model,where the number of constraints is just O(n2).Therefore,the existing efficient MILP algorithms can be used to solve NVEP.Secondly,we provide some properties of N-vehicle problem and give three methods for cutting plane construction,which can increase the solving speed significantly.Finally,a numerical experiment is provided to verify the effectiveness and robustness for different instances and scales of acceleration techniques.
基金Supported by Key Laboratory of Management,Decision and Information Systems,Chinese Academy of Science
文摘The research of efficient computation focus on special structures of NP-hard problem instances and request providing reasonable computing cost of instances in polynomial time. Based on the theory of combinatorial optimization, by studying the clusters partition and the clusters complexity measurement in Nvehicle exploration problem, we build a frame of efficient computation and provide an application of tractability for NP-hard problem. Three N-vehicle examples show that when we use efficient computation mechanism on N-vehicle, through polynomial steps of tractability analysis, decision makers can get the computing cost of searching optimal solution before practical calculation.
基金partly supported by Daqing Oilfield Company Project of PetroCHINA under Grant No.dqc- 2010-xdgl-ky-002Key Laboratory of Management,Decision and Information Systems,Chinese Academy of Sciences
文摘这份报纸扩大单个任务的 n 车辆探索问题到多工 n 车辆探索问题(MTNVEP ) ，由把 n 车辆探索问题与安排问题的工作相结合。起初，作者证明 MTNVEP 为任务的固定数字是 NP 难的，并且它为任务的一般数字是强烈 NP 难的。然后，他们与计算时间 O (n3 n ) 建议一个改进精确算法，它比 O 好(n !) 当 n 变得足够地大。而且，四个启发式的算法被建议。启发式的算法的有效性被实验最后说明。
文摘Editor’s words The author puts forward some problems involving in CIETAC Arbitration Rules 2000 such as the third nation- ality of the presiding arbitrator, the full autonomy of the parties to choose Arbitration Rules and the improvement of applying for interim measures and so on, which are welcomed by CIETAC, though some of which CIETAC does do that in practice, for instance, appointing the third nationalities as presiding arbitrator, and some of which the improvement shall be followed by the law, for instance, the problem of interim measures. We hope there are more articles contributed to arbitration in China directly deal with the theory and practice of arbitration in China as well as all over the world.
