Combinatorial optimization-typical problem-job shop problem

Typical problem and execution method

Job shop problem

Process the given $ n $ jobs $ V = \ {1, \ dots, n \} $ on $ m $ machines. A machine can only process one job at a time. Find a schedule that minimizes the end time of all jobs. When the processing order of machines is fixed for any job, it is called a flow shop problem.

Execution method (2 example of machine flow shop problem)

usage


Signature: two_machine_flowshop(p)
Docstring:
2 Machine flow shop problem
Find a job schedule for two flow shops(Johnson method)
input
    p: (Pre-process processing time,Post-process processing time)List by product
output
List of processing time and processing order

python


from ortoolpy import two_machine_flowshop
two_machine_flowshop([(4, 3), (3, 1), (1, 4)])

result


(9, [2, 0, 1])

python


# pandas.DataFrame
from ortoolpy.optimization import TwoMachineFlowshop
TwoMachineFlowshop('data/flowshop.csv')[1]
first second
2 1 4
0 4 3
1 3 1

data

Recommended Posts

Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-typical problems and execution methods