Job shop scheduling problem.md

POLab
2018/12/01
【回到首頁】

(一)問題描述

● 題目:

There are j jobs and m machines; each job comprises a set of tasks1 which must each be done on a different machine for different specified processing times, in a given job-dependent order. Table 1 shows a standard 6 x 6 benchmark problem (ie, j = 6; m = 6), from (Muth & Thompson 1963).

● 已知:

• 加工順序

• 加工時間

● 目標:

• 最小化完工時間

● 限制:

• 每台機台一次只能做一個工作
• 每個工作必須遵守一定的順序

(二)數學規劃

● Notation

• i = machine
• j = job
• p_ij = processing time

● 決策變數

• y_ij : starting time of operation(i,j)

dv = pulp.LpVariable.dicts("start_time",
                                     ((i, j) for i in range(6) for j in range(6)),
                                     lowBound=0,
                                     cat='Continuous')

• Cmax : makespan

Cmax = pulp.LpVariable('Cmax',lowBound = 0, cat='Continuous')

• b : binary

b =  pulp.LpVariable.dicts("binary_var",
                                     ((i, j,o) for i in range(6) for j in range(6) for o in range(6) if j<o),
                                     lowBound=0,
                                     cat='Binary')

● 數學式

• 目標式 : Min Cmax

model = pulp.LpProblem("MIN_makespan", pulp.LpMinimize)
model += Cmax

• 限制式:

#加入限制式
#確保工作的Operation順序，必須前一站完成才能排下一站
for j in range(6):
    for i in range(5):
       I = mo[j,i]
       K = mo[j,i+1]
       J = j
       model += (dv[K,J] - dv[I,J]) >= pt[I,J]
#定義makespan       
for j in range(6):
    for i in range(6):
       I = mo[j,i]
       J = j
       model += (Cmax - dv[I,J]) >= pt[I,J]
#確保一台機台一次只能有一個工作進行       
for i in range(6):
    for j in range(6):
        for l in range(6):
            if j!=l:
                I=i
                L = l
                J = j
                model += (dv[I,J] - dv[I,L]) >= (pt[I,L] - 100*(1-b[i,J,L]))
                model += (dv[I,L] - dv[I,J]) >= (pt[I,J] - 100*(b[i,J,L]))

求解

model.solve()
pulp.LpStatus[model.status]     

#印出解及目標值

for var in dv:
    var_value = dv[var].varValue
    print( var[0],'-',var[1] ,var_value)

total_cost = pulp.value(model.objective)
print ('min cost:',total_cost)

#min cost:55

● 甘特圖

• 此處繪圖套件使用plotly，詳細套件說明請參考這裡

Reference

Michael L.Pinedo SchedulingTheory, Algorithms, and Systems Fourth Edition

J.F.Muth & G.L.Thompson. Industrial Scheduling. Prentice Hall, Englewood Cliffs, New Jersey,1963.