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

問題:

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

各製品に対する各機械の生産日数を下の表に示す、そして生産の終わる許容日数を9日とし、各製品の機械で生産順序は
    X1:機械1⇒機械2⇒機械3
    X2:機械3⇒機械1⇒機械2

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

機械1 機械2 機械3
X1
X2
変数説明
X1ij : 製品1を機械iで第j日に生産するとき1、それ以外のときは0となる変数(0,1変数)
X2ij : 製品2を機械iで第j日に生産するとき1、それ以外のときは0となる変数(0,1変数)

問題分析

X1,X2二製品の生産を終えるのに要する最早日数ははそれぞれ6日であるから、少なくとも6日は要する、そして最後に使用する機械は、それぞれ機械3、機械2、そこで最小化すべき目的関数として、第一目標は許容日数9日目はなるべ生産しないようにする。同じく第二目標は8日目、第三目標は7日目とする。
機械1でX1を生産するのに2日を要することにより
    Σ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)
また、同時点で2種以上の製品を同一機械で生産することはできないから
    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)
X1についての生産を行なう順序を考慮すると
    2X12j ≦ ΣX11i [3≦j≦(9-1) , 1≦i≦(j-1)]
    3X13j ≦ ΣX12i [6≦j≦(9) , 1≦i≦(j-1)]
X2についての生産を行なう順序を考慮すると
    3X21j ≦ ΣX23i [4≦j≦(9-2) , 1≦i≦(j-1)]
    X22j ≦ ΣX21i [5≦j≦(9) , 1≦i≦(j-1)]
生産順序を考えると以下の変数は無条件0変数である。
    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順序制約
  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
製品2順序制約
  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の計算結果

//
//***** GLPS Columns変数最適化解 *****
//
[ モデル名 : SAMPL07 ]
NumberColumnsNameAtActivityReduced Cost
1X111BS10
2X112BS10
3X11300
4X11403
5X11500
6X11600
7X11703
8X11800
9X11903
10X12100
11X12200
12X123BS10
13X124BS10
14X125BS10
15X12600
16X12700
17X12800
18X12900
19X13100
20X13200
21X13300
22X13400
23X13500
24X136BD10
25X13700
26X13800
27X13901
28X21100
29X21200
30X21300
31X214BS10
32X21500
33X21600
34X21700
35X21800
36X21900
37X22100
38X22200
39X22300
40X22400
41X22500
42X226BS10
43X227BS10
44X22800
45X22901
46X231BS10
47X232BS10
48X233BD10
49X23400
50X23500
51X23600
52X23700
53X23800
54X23900
*
**************************
* GLPS 目標達成分析
**************************
*
第一目標 9日目しない 目標達成
第二目標 8日目しない 目標達成
第三目標 7日目しない 結果値 1

**********************************************
計算結果各製品の機械で生産順序は以下になる。
**********************************************
1日2日3日 4日5日6日 7日8日9日
X11
X12
X13
X23
X21
X22

評価

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

[ 最適化ソフトメンページへ]

Copyright(C)1998-2008 M.Shiimori , All Rights Reserved.