1# --------------------------------------------------------------------------
2# Source file provided under Apache License, Version 2.0, January 2004,
3# http://www.apache.org/licenses/
4# (c) Copyright IBM Corp. 2015, 2022
5# --------------------------------------------------------------------------
6
7"""
8In the classical Job-Shop Scheduling problem a finite set of jobs is processed
9on a finite set of machines.
10Each job is characterized by a fixed order of operations, each of which is to
11be processed on a specific machine for a specified duration.
12All machines are used by each job.
13Each machine can process at most one operation at a time and once an operation
14initiates processing on a given machine it must complete processing uninterrupted.
15
16The objective of the problem is to find a schedule that minimizes the makespan (end date) of the schedule.
17
18Please refer to documentation for appropriate setup of solving configuration.
19"""
20
21from docplex.cp.model import *
22import os
23
24
25#-----------------------------------------------------------------------------
26# Initialize the problem data
27#-----------------------------------------------------------------------------
28
29# Read the input data file.
30# Available files are jobshop_ft06, jobshop_ft10 and jobshop_ft20
31# First line contains the number of jobs, and the number of machines.
32# The rest of the file consists of one line per job.
33# Each line contains list of operations, each one given by 2 numbers: machine and duration
34filename = os.path.dirname(os.path.abspath(__file__)) + '/data/jobshop_ft06.data'
35with open(filename, 'r') as file:
36 NB_JOBS, NB_MACHINES = [int(v) for v in file.readline().split()]
37 JOBS = [[int(v) for v in file.readline().split()] for i in range(NB_JOBS)]
38
39
40#-----------------------------------------------------------------------------
41# Prepare the data for modeling
42#-----------------------------------------------------------------------------
43
44# Build list of machines. MACHINES[j][s] = id of the machine for the operation s of the job j
45MACHINES = [[JOBS[j][2 * s] for s in range(NB_MACHINES)] for j in range(NB_JOBS)]
46
47# Build list of durations. DURATION[j][s] = duration of the operation s of the job j
48DURATION = [[JOBS[j][2 * s + 1] for s in range(NB_MACHINES)] for j in range(NB_JOBS)]
49
50
51#-----------------------------------------------------------------------------
52# Build the model
53#-----------------------------------------------------------------------------
54
55# Create model
56mdl = CpoModel()
57
58# Create one interval variable per job operation
59job_operations = [[interval_var(size=DURATION[j][m], name='O{}-{}'.format(j,m)) for m in range(NB_MACHINES)] for j in range(NB_JOBS)]
60
61# Each operation must start after the end of the previous
62for j in range(NB_JOBS):
63 for s in range(1, NB_MACHINES):
64 mdl.add(end_before_start(job_operations[j][s-1], job_operations[j][s]))
65
66# Force no overlap for operations executed on a same machine
67machine_operations = [[] for m in range(NB_MACHINES)]
68for j in range(NB_JOBS):
69 for s in range(NB_MACHINES):
70 machine_operations[MACHINES[j][s]].append(job_operations[j][s])
71for mops in machine_operations:
72 mdl.add(no_overlap(mops))
73
74# Minimize termination date
75mdl.add(minimize(max(end_of(job_operations[i][NB_MACHINES-1]) for i in range(NB_JOBS))))
76
77
78#-----------------------------------------------------------------------------
79# Solve the model and display the result
80#-----------------------------------------------------------------------------
81
82# Solve model
83print('Solving model...')
84res = mdl.solve(TimeLimit=10)
85print('Solution:')
86res.print_solution()
87
88# Draw solution
89import docplex.cp.utils_visu as visu
90if res and visu.is_visu_enabled():
91 visu.timeline('Solution for job-shop ' + filename)
92 visu.panel('Jobs')
93 for i in range(NB_JOBS):
94 visu.sequence(name='J' + str(i),
95 intervals=[(res.get_var_solution(job_operations[i][j]), MACHINES[i][j], 'M' + str(MACHINES[i][j])) for j in
96 range(NB_MACHINES)])
97 visu.panel('Machines')
98 for k in range(NB_MACHINES):
99 visu.sequence(name='M' + str(k),
100 intervals=[(res.get_var_solution(machine_operations[k][i]), k, 'J' + str(i)) for i in range(NB_JOBS)])
101 visu.show()