Flexible-Job-Work-Scheduling-Problem-with-Sequence-Dependent-setups-using-Python/Flexible Job Work Scheduling Problem.py at main · SK-SCMLab/Flexible-Job-Work-Scheduling-Problem-with-Sequence-Dependent-setups-using-Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import pulp

#------ DATA SECTION -------

products = ['P1', 'P2', 'P3']
machines = ['M1', 'M2']

# Each job's list of eligible machines
eligible = {
    'P1': ['M1'],
    'P2': ['M1', 'M2'],
    'P3': ['M2']
}

# Processing times for each (job, machine) pair
proc_time = {
    ('P1', 'M1'): 12,
    ('P2', 'M1'): 10, ('P2', 'M2'): 15,
    ('P3', 'M2'): 13
}

# Sequence-dependent setup times
setup_time = {}
for m in machines:
    for i in products:
        for j in products:
            if m in eligible.get(i, []) and m in eligible.get(j, []):
                setup_time[(m, i, j)] = 5 if i != j else 0

big_M = 1000 # Big-M value

#----- MODEL SECTION ------
prob = pulp.LpProblem("FJSSP_SeqDepSetup", pulp.LpMinimize)

# Variables
assign = pulp.LpVariable.dicts('assign', ((j, m) for j in products for m in machines), 0, 1, pulp.LpBinary)
start = pulp.LpVariable.dicts('start', products, 0)
comp = pulp.LpVariable.dicts('comp', products, 0)
comp_jm = pulp.LpVariable.dicts('comp_jm', ((j,m) for j in products for m in machines), 0)
y = pulp.LpVariable.dicts('y', ((j, k, m) for j in products for k in products if j != k for m in machines), 0, 1, pulp.LpBinary)
Cmax = pulp.LpVariable('Cmax', 0)

# Objective
prob += Cmax

#----- CONSTRATINTS ------

# 1. Each job assigned to one eligible machine
for j in products:
    prob += pulp.lpSum(assign[j, m] for m in eligible[j]) == 1

# 2. Completion time for each job
for j in products:
    for m in eligible[j]:
        prob += comp_jm[j, m] >= start[j] + proc_time[j, m] - big_M * (1 - assign[j, m])
        prob += comp_jm[j, m] <= start[j] + proc_time[j, m] + big_M * (1 - assign[j, m])
    prob += comp[j] == pulp.lpSum(comp_jm[j, m] for m in eligible[j])

# 3. Makespan >= completion time
for j in products:
    prob += Cmax >= comp[j]

# 4. Sequencing with setup times
for m in machines:
    jobs_on_m = [j for j in products if m in eligible.get(j, [])]
    for j in jobs_on_m:
        for k in jobs_on_m:
            if j != k:
                prob += y[j, k, m] + y[k, j, m] >= assign[j, m] + assign[k, m] - 1
                prob += start[k] >= comp[j] + setup_time[(m, j, k)] - big_M * (1 - y[j, k, m])
                prob += y[j, k, m] <= assign[j, m]
                prob += y[j, k, m] <= assign [k, m]

# 5. Non-negative start times
for j in products:
    prob += start[j] >= 0

# --------- SOLVE --------
solver = pulp.PULP_CBC_CMD(msg=True)
prob.solve(solver)

# ---- OUTPUT ----
#print("Status:", pulp.LpStatus[prob.status])
# print(f"Minimum makespan: {pulp.value(Cmax):.2f}\n")

#for j in products:
    #assigned_m = [m for m in machines if pulp.value(assign[j, m]) > 0.5]
    #assigned_machine = assigned_m[0] if assigned_m else "None"
    #print(f"Job {j}: Machine {assigned_machine}, Start: {pulp.value(start[j]):.2f}, Finish: {pulp.value(comp[j]):.2f}")

#print("\nOptimal sequencing on each machine:")
#for m in machines:
    #jobs_m = [j for j in products if pulp.value(assign[j, m]) > 0.5]
    #if not jobs_m:
        #print(f"Machine {m}: No jobs assigned")
        #continue
    #jobs_m = sorted(jobs_m, key=lambda j: pulp.value(start[j]))
    #print(f" Machine {m}: {' -> '.join(jobs_m)}")

status = pulp.LpStatus[prob.status]
print("Status:", status)

if status != "Optimal" and status != "Feasible":
    print("No feasible solution found.")
else:
    print(f"Minimum makespan: {pulp.value(Cmax):.2f}\n")

    for j in products:
        assigned_m = [m for m in machines if pulp.value(assign[j, m]) is not None and pulp.value(assign[j, m]) > 0.5 ]
        assigned_machine = assigned_m[0] if assigned_m else "None"
        print(f"Job {j}: Machine {assigned_machine}, Start: {pulp.value(start[j]):.2f}, Finish: {pulp.value(comp[j]):.2f}")

    print("\nOptimal sequencing on each machine:")
    for m in machines:
        jobs_m = [j for j in products if pulp.value(assign[j, m]) is not None and pulp.value(assign[j, m]) > 0.5]
        if not jobs_m:
            print(f" Machine {m}: No jobs assigned")
            continue
        jobs_m = sorted(jobs_m, key=lambda j: pulp.value(start[j]) if pulp.value(start[j]) is not None else 0)
        print(f" Machine {m}: {' -> '.join(jobs_m)}")