3C3 A TRANSSHIPMENT PROBLEM WITH A PREMUTABLE TRANSIT VECTOR
スポンサーリンク
概要
- 論文の詳細を見る
We treat the computational complexity of a transshipment problem with a permutable transit vector. The problem, called TRANSIT for short, is a generalization of the transportation problem with a permutable demand vector. It has been known that the transportation problem with a permutable demand vector can be solved in polynomial time if each entry of the demand vector takes zero, one, or two. In this paper, we prove that problem TRANSIT in NP-hard even when each entry of the permutable transit vector takes either zero or two. We also show that problem TRANSIT can be solved in polynomial time if each entry of the transit vector takes either zero or one.
- 一般社団法人日本機械学会の論文
- 2009-07-04
著者
-
KARUNO Yoshiyuki
Department of Mechanical and System Engineering, Kyoto Institute of Technology
-
Yamashita Kougaku
Kyoto Institute of Technology
-
Yamashita Kougaku
Dep. Of Mechanical And System Engineering Kyoto Inst. Of Technol.
-
Karuno Yoshiyuki
Dep. Of Mechanical And System Engineering Kyoto Inst. Of Technol.
-
Karuno Yoshiyuki
Department Of Mechanical And System Engineering Faculty Of Engineering And Design Kyoto Institute Of
-
YAMASHITA Kougaku
Department of Mechanical and System Engineering Kyoto Institute of Technology
-
TACHIBANA Tomoaki
Department of Mechanical and System Engineering Kyoto Institute of Technology
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- AN INAPPROXIMABILITY OF TRANSSHIPMENT PROBLEMS WITH PERMUTABLE TRANSIT VECTORS
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- 4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS
- B34 Hardness of Approximating Transshipment Problems with Permutable Transit Vectors(Advanced machining technology)
- 3C3 A TRANSSHIPMENT PROBLEM WITH A PREMUTABLE TRANSIT VECTOR
- 2-B-5 A HEURISTIC ALGORITHM FOR OPERATING A PERMUTATIONAL CIRCULATION-TYPE VEHICLE ROUTING SYSTEM
- 1B2 AN APPLICATION OF THE GENETIC ALGORITHM TO A TWO-MACHINE ROBOTIC FLOW-SHOP SCHEDULING PROBLEM(Technical session 1B : Meta Heuristics)
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- A Dynamic Programming Based Improvement Heuristic for a Repetitive Routing Problem of Grasp-and-Delivery Robots
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- Dynamic Programming Algorithms with Data Rounding for Combinatorial Food Packing Problems
- Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
- 4A2 NETWORK TRANSFORMATION HEURISTICS FOR MULTI-STORY STORAGE RACK PROBLEMS(Technical session 4A: Material handling system)
- 5B1 IMPROVED IMPLEMENTATION OF AN APPROXIMATION ALGORITHM WITH FACTOR TWO FOR A CYCLIC ROUTING PROBLEM OF GRASP-AND-DELIVERY ROBOTS(Technical session 5B: Routing problems)
- 5B3 APPROXIMATING CYCLIC ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS(Technical session 5B: Routing problems)
- Scheduling Capacitated One-Way Vehicles on Paths with Deadlines