3B3 Complexity of a dynamic lot-scheduling problem formulated by a 0-1 pure integer programming(Technical session 3B : Combinatorics 2)
スポンサーリンク
概要
- 論文の詳細を見る
A complexity of a dynamic lot-scheduling problem formulated by a 0-1 pure integer programming is discussed. It is proved that the problem with n items is NP-complete in a strong sense. In order to evaluate the computational complexity more detailed, a dynamic programming algorithm is developed to solve the problem and then it is shown that the problem can be solved in a time O(n^2(T/n+1)^n) using the developed algorithm, where notations n and T are the number of product items and planning horizon, respectively. The discussion in this paper is applicable to the traditional lot-scheduling problem used in MRP.
- 一般社団法人日本機械学会の論文
- 2004-05-24
著者
-
Fujita Seiichi
Waseda University
-
Ohno Katsuhisa
Nagoya Institute of Technology
-
Tamura Takayoshi
Nagoya Institute of Technology
-
Kojima Mitsutoshi
Nagoya Institute of Technology
関連論文
- STOCHASTIC PROPERTIES OF FORK/JOIN MULTI-STAGE PRODUCTION SYSTEMS WITH GENERAL BLOCKING
- A HEURISTIC SCHEDULING ALGORITHM FOR STEEL MAKING PROCESS WITH CRANE HANDLING(Advanced Planning and Scheduling for Supply Chain Management)
- 7A2 A Heuristic Scheduling Algorithm for Multi-stage Job-shop Process with Crane Handling(Technical session 7A: Machine and shop scheduling 2)
- AN INTEGRATED ANALYTICAL/SIMULATION APPROACH FOR ECONOMIC DESIGN OF AN AGV SYSTEM
- A Planning Model for Lot Production on Short Planning Horizon : Series C : Vibration, Control Engineering, Engineering for Industry
- 3B3 Complexity of a dynamic lot-scheduling problem formulated by a 0-1 pure integer programming(Technical session 3B : Combinatorics 2)
- ON A GENERALIZATION OF THE SECRETARY PROBLEM WITH UNCERTAIN SELECTION
- ANALYSIS AND OPTIMIZATION OF A U-SHAPED PRODUCTION LINE
- A Continuous Time Duration Problem With an Unknown Number of Options