用 Python 做商管程式設計（一） Week 5b

05-b01 作業管理與演算法
Operation Management (OM)
利用程式解OM問題-演算法

演算法 Algorithm
    A detailed description of actions such that action is doable.

Scheduling 
Makespan 最小化

• m 台機器
• n  個 jobs
• job j 的 processing time
•  一台機器完成 job j 共需要 pj 時間
• Complete time Cj  = Sj(開始時間) + pj

要分配這些jobs  給所有 機器 使得 最後的 completing time  最小

Longest processing time first (LPT)

• jobs 的 processing time 降冪排列
• 分配job 給目前最早完成時間之機器

--- code ---

# read and prepare n,m,p

n = int(input("Number of jobs: "))

m = int(input("Number of machines: "))

pStr = input("Processing times: ")

p  =  pStr.split(' ')

for i in range(n):

p[i] = int(p[i])

#sort and reverse

#p.sort()

#p.reverse()

# machine complete times 

loads  =  [0] * m

assignment = [0]  * n

#in iterarion j , assign job j to the least loaded machine 

for j in range(n):

#find the least loaded machine

leastLoadedMachine = 0

leastLoad = loads[0]

for i in range(1,m):

if loads[i] < leastLoad:

leastLoadedMachine = i

leastLoad = loads[i]

#schedule a job

loads[leastLoadedMachine] +=p[j]

assignment[j] = leastLoadedMachine + 1

#check the process

print(str(p[j]) + ": " + str(loads))

#the result 

print("Job assignment: "+str(assignment))

print("Machine loads: "+str(loads))

-------------

heuristic 不能保證得到最佳解

11