<jupyter_start><jupyter_text>Process scheduling  Problem definition A set of n jobs must be processed in a machine that can handle one job at a time.Task j needs pj hours to be processed.A directed and acyclic graph G = (V, E), with V = {1, . . . , n}, establishes a partialorder for job processing in the machine. That is, if there exists a path δi,j from i toj in G, then job i must be processed before job j.Given nonnegative weights wj , j = 1, . . . , n, in which order should we process thejobs in order to minimize the weighted sum of the start processing time of all jobs,while respecting the precedence order? For the modeling task that follows, sj is theinstant that job j starts to be processed.Tasks:(a) Formulate the problem in mixed-integer linear programming using discrete andcontinuous variables.(b) Model the problem in AMPL and solve the instance given below, in whichV = {1, . . . , 12}. Present the results.  | job (j)  | length (pj)| weight (wj) | Arcs (j,i)    ||----|----|----|---------------|| 1  | 3  | 5  | (1,3)         || 2  | 2  | 3  |               || 3  | 6  | 7  | (3,12), (3,7) || 4  | 2  | 6  |               || 5  | 5  | 1  |               || 6  | 4  | 2  | (6,7)         || 7  | 4  | 8  |               || 8  | 3  | 4  | (8,6)         || 9  | 10 | 7  |               || 10 | 1  | 1  | (10,12)       || 11 | 8  | 6  |               || 12 | 7  | 2  |               |  Model \begin{equation}\min  \sum_{j =1}^{N} s_j \times w_j \\\mathrm{s.t.} : N \in \mathbb{Z}^{+} \\s_{j} \ge (s_i+p_i).b_{i,j} \\s_{i} \ge (s_j+p_j).\hat{b}_{i,j} \\s_j \in \mathbb{R}_{\ge 0} \space \forall j \\p_j \in \mathbb{R}_{+} \\w_j \in \mathbb{R}_{+} \\b_{i,j} \in \{0,1\} \space \forall i,j \\\hat{b}_{i,j} \in \{0,1\} \space \forall i,j \\b_{i,j}=1-\hat{b}_{i,j}\space \forall i,j \\b_{j,j}=0\space \forall j \\arc_{i,j} \in \{0,1\} \space \forall i,j \\b_{i,j} \ge arc_{i,j}\end{equation}  Modeling (instance)<jupyter_code>import gurobipy as gp
from gurobipy import GRB, Model
import pandas as pd
import numpy as np<jupyter_output><empty_output><jupyter_text>Create supporting (instance) data<jupyter_code>N = 12; # 'size' of the problem, here it's both the number of processes and number of slots

# Create a list with the well indexes as given by the problem (prevents python's 0-indexing)
V = [item for item in range(1, N+1)]

# supporting data:
w = {j:[5,3,7,6,1,2,8,4,7,1,6,2][j-1] for j in V} # these are the given process 'weights' (importances)
p = {j:[3,2,6,2,5,4,4,3,10,1,8,7][j-1] for j in V} # these are the given process time lenghts

"""
'dependance table'
     p1 p2 p3 p4
p1  [0  1  0  0] <- p1 must come before p2
p2  [0  0  0  0]
p3  [1  0  0  0] <- p3 must come before p1
p4  [0  0  0  0]
"""
D = np.zeros((N,N))
arcs = ((1,3),(3,12),(3,7),(6,7),(8,6),(10,12)) # these arcs are in order (i,j), where i depends on j
for arc in arcs:
    x=int(arc[0]) - 1 # minus one is because of python 0 indexing
    y=int(arc[1]) - 1 # minus one is because of python 0 indexing
    D[x][y] = 1
print('dependance table\n',D)<jupyter_output>dependance table
 [[0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]<jupyter_text>Model creation<jupyter_code>m = Model("process_scheduling") 

# Decision variables:
# 1)represents the starting time of each process
'''
s: [1, 3, 4, ...] process 1 starts at time=1, process 2 starts at time=3...
'''
s = m.addVars(V, vtype=GRB.CONTINUOUS, name="s") 

# 2)decision varibles. If B[i,j]=1, then process i comes before process j
"""
'comes before table'
     p1 p2 p3 p4
p1  [0  1  1  1] p1 comes before p2, p3 and p4 - first
p2  [0  0  0  0] p2 comes before no one-last
p3  [0  1  0  1] p3 comes before p2 and p4 - second
p4  [0  1  0  0] p4 - third
p1->p3->p4->p2
"""

B=m.addVars(V, V, vtype=GRB.BINARY, name='B')
NB=m.addVars(V, V, vtype=GRB.BINARY, name='NB') # negation of B

m.update()<jupyter_output>Set parameter Username
Academic license - for non-commercial use only - expires 2022-05-20<jupyter_text>Constraints<jupyter_code>#Constraints over the binary tables
for i in V:
    for j in V:
        m.addConstr(B[i,j]==1-NB[i,j], name=f"BNB{i}_{j}") # if job i comes before job j, then job j cannot come before job i

m.update()
# Constraints related to the
# 1)non-overlaping usages of resources
for j in V:
    for i in (set(V)-set([j])):
        m.addConstr(s[j]>=(s[i]+p[i])*B[i,j])
        m.addConstr(s[i]>=(s[j]+p[j])*NB[i,j])

# 2)given process precedence requirements 
for i in V:
    for j in V:
        Di = i - 1
        Dj = j - 1
        if D[Di][Dj] == 1:
            m.addConstr(B[i,j]==1,name=f'arc({i},{j})')

# 3) a job cannot happen before itself            
for i in V:
    m.addConstr(B[i,i]==0)

m.update()<jupyter_output><empty_output><jupyter_text>Solution<jupyter_code>m.setObjective(sum([s[j]*w[j] for j in V]), GRB.MINIMIZE)

m.update()
m.optimize()
for j in V:
    start=round(s[j].x)
    end = start+p[j]
    print(f'Process {j} starts at {start} and ends at {end}')<jupyter_output>Process 1 starts at 2 and ends at 5
Process 2 starts at 5 and ends at 7
Process 3 starts at 10 and ends at 16
Process 4 starts at 0 and ends at 2
Process 5 starts at 50 and ends at 55
Process 6 starts at 16 and ends at 20
Process 7 starts at 20 and ends at 24
Process 8 starts at 7 and ends at 10
Process 9 starts at 33 and ends at 43
Process 10 starts at 24 and ends at 25
Process 11 starts at 25 and ends at 33
Process 12 starts at 43 and ends at 50
{'fraction_non_alphanumeric': 0.16766467065868262, 'fraction_numerical': 0.07117194183062446, 'mean_word_length': 2.4964114832535884, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '443178', 'license': 'MIT', 'n_tokens_mistral': 2685, 'n_tokens_neox': 2363, 'n_words': 894, 'path': 'process_scheduling_optimization.ipynb', 'repo_name': 'brunokiyoshi/process_scheduling_optimization', 'size': '5845'}