機械スケジューリング問題

問題:

Ｘ１，Ｘ２二種類の製品を三種類の機械で生産します。各製品が作られる際、その使用される機械の順序が決まっています。どのような生産スケジュールを行えば最も早期に各製品の生産が終われる生産スケジュールを決定出来るでしょうか？

Ｘ１：機械１⇒機械２⇒機械３
Ｘ２：機械３⇒機械１⇒機械２

各製品に対する各機械の生産日数

問題分析

ΣX11i = 2 (1≦i≦9)
同様に
ΣX12i = 3 (1≦i≦9)
ΣX13i = 1 (1≦i≦9)
ΣX21i = 1 (1≦i≦9)
ΣX22i = 2 (1≦i≦9)
ΣX23i = 3 (1≦i≦9)

X11i+X12i+X13i≦1 (1≦i≦9)
X21i+X22i+X23i≦1 (1≦i≦9)
X11i+X21i ≦1 (1≦i≦9)
X12i+X22i ≦1 (1≦i≦9)
X13i+X23i ≦1 (1≦i≦9)

2X12j ≦ ΣX11i [3≦j≦(9-1) , 1≦i≦(j-1)]
3X13j ≦ ΣX12i [6≦j≦(9) , 1≦i≦(j-1)]

3X21j ≦ ΣX23i [4≦j≦(9-2) , 1≦i≦(j-1)]
X22j ≦ ΣX21i [5≦j≦(9) , 1≦i≦(j-1)]

X121,X122,X131,X132,X133,X134,X135
X211,X212,X213,X221,X222,X223,X224
X116,X117,X118,X119,X129
X237,X238,X239,X218,X219

問題定式化

第一目標　X139+X229　→　最小化
第二目標　X138+X228　→　最小化
第三目標　X137+X227　→　最小化

制約行

製品の機械別処理日数

1. X111+X112+X113+X114+X115+X116+X117+X118+X119　= 2
   
2. X121+X122+X123+X124+X125+X126+X127+X128+X129　= 3
   
3. X131+X132+X133+X134+X135+X136+X137+X138+X139　= 1
   
4. X211+X212+X213+X214+X215+X216+X217+X218+X219　= 1
   
5. X221+X222+X223+X224+X225+X226+X227+X228+X229　= 2
   
6. X231+X232+X233+X234+X235+X236+X237+X238+X239　= 3
   

1. X111+X121+X131≦1
   
2. X112+X122+X132≦1
   
3. X113+X123+X133≦1
   
4. X114+X124+X134≦1
   
5. X115+X125+X135≦1
   
6. X116+X126+X136≦1
   
7. X117+X127+X137≦1
   
8. X118+X128+X138≦1
   
9. X119+X129+X139≦1
   
10. X211+X221+X231≦1
    
11. X212+X222+X232≦1
    
12. X213+X223+X233≦1
    
13. X214+X224+X234≦1
    
14. X215+X225+X235≦1
    
15. X216+X226+X236≦1
    
16. X217+X227+X237≦1
    
17. X218+X228+X238≦1
    
18. X219+X229+X239≦1
    
19. X111+X211≦1
    
20. X112+X212≦1
    
21. X113+X213≦1
    
22. X114+X214≦1
    
23. X115+X215≦1
    
24. X116+X216≦1
    
25. X117+X217≦1
    
26. X118+X218≦1
    
27. X119+X219≦1
    
28. X121+X221≦1
    
29. X122+X222≦1
    
30. X123+X223≦1
    
31. X124+X224≦1
    
32. X125+X225≦1
    
33. X126+X226≦1
    
34. X127+X227≦1
    
35. X128+X228≦1
    
36. X129+X229≦1
    
37. X131+X231≦1
    
38. X132+X232≦1
    
39. X133+X233≦1
    
40. X134+X234≦1
    
41. X135+X235≦1
    
42. X136+X236≦1
    
43. X137+X237≦1
    
44. X138+X238≦1
    
45. X139+X239≦1
    

1. X111+X112-2X123≧0
   
2. X111+X112+X113-2X124≧0
   
3. X111+X112+X113+X114-2X125≧0
   
4. X111+X112+X113+X114+X115-2X126≧0
   
5. X111+X112+X113+X114+X115+X116-2X127≧0
   
6. X111+X112+X113+X114+X115+X116+X117-2X128≧0
   
7. X121+X122+X123+X124+X125-3X136≧0
   
8. X121+X122+X123+X124+X125+X126-3X137≧0
   
9. X121+X122+X123+X124+X125+X126+X127-3X138≧0
   
10. X121+X122+X123+X124+X125+X126+X127+X128-3X139≧0
    

1. X231+X232+X233-3X214≧0
   
2. X231+X232+X233+X234-3X215≧0
   
3. X231+X232+X233+X234+X235-3X216≧0
   
4. X231+X232+X233+X234+X235+X236-3X217≧0
   
5. X211+X212+X213+X214-X225≧0
   
6. X211+X212+X213+X214+X215-X226≧0
   
7. X211+X212+X213+X214+X215+X216-X227≧0
   
8. X211+X212+X213+X214+X215+X216+X217-X228≧0
   

GLPS正式版GLPSの計算結果

評価

X1,X2二製品の生産を終える日数は７日、許容日数は９日を超えていない。最適生産スケジュールです。