import%20marimo%0A%0A__generated_with%20%3D%20%220.11.25%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20random%0A%20%20%20%20import%20pyscipopt%20as%20scip%0A%20%20%20%20return%20random%2C%20scip%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%20%E9%A0%86%E5%88%97%E3%83%95%E3%83%AD%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%83%E3%83%97%E5%95%8F%E9%A1%8C%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%24n%24%20%E5%80%8B%E3%81%AE%E3%82%B8%E3%83%A7%E3%83%96%E3%82%92%20%24m%24%20%E5%8F%B0%E3%81%AE%E3%83%9E%E3%82%B7%E3%83%B3%E3%81%A7%E9%A0%86%E7%95%AA%E3%81%AB%E5%87%A6%E7%90%86%E3%81%99%E3%82%8B.%0A%20%20%20%20%20%20%20%20%E5%90%84%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AF%E3%83%9E%E3%82%B7%E3%83%B3%201%2C%20%E3%83%9E%E3%82%B7%E3%83%B3%202%2C%20...%20%E3%81%A7%E9%A0%86%E3%81%AB%E5%87%A6%E7%90%86%E3%81%95%E3%82%8C%E3%83%9E%E3%82%B7%E3%83%B3%20%24m%24%20%E3%81%A7%E5%87%A6%E7%90%86%E3%81%95%E3%82%8C%E3%82%8B%E3%81%A8%E5%AE%8C%E4%BA%86%E3%81%AB%E3%81%AA%E3%82%8B.%0A%0A%20%20%20%20%20%20%20%20!%5B%5D(https%3A%2F%2Fwww.researchgate.net%2Fprofile%2FMariusz-Makuchowski%2Fpublication%2F280775329%2Ffigure%2Ffig1%2FAS%3A284468087672848%401444833885900%2FSchedules-of-the-different-variants-of-the-flow-shop-problem.png)%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%23%20%E4%BD%8D%E7%BD%AE%E3%83%87%E3%83%BC%E3%82%BF%E5%AE%9A%E5%BC%8F%E5%8C%96%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20%E5%AE%9A%E6%95%B0%0A%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%3A%20%24J%20%3D%20%5C%7B%201%2C%20%5Cdots%2C%20n%20%5C%7D%24%0A%20%20%20%20%20%20%20%20-%20%E3%83%9E%E3%82%B7%E3%83%B3%3A%20%24M%20%3D%20%5C%7B%201%2C%20%5Cdots%2C%20m%20%5C%7D%24%0A%20%20%20%20%20%20%20%20-%20%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%3A%20%24p_%7Bij%7D%20%5C%20(%5Cforall%20i%20%5Cin%20M%2C%20%5Cforall%20j%20%5Cin%20J)%24%0A%0A%20%20%20%20%20%20%20%20%23%23%20%E6%B1%BA%E5%AE%9A%E5%A4%89%E6%95%B0%0A%0A%20%20%20%20%20%20%20%20-%20%24x_%7Bj%20%5Ckappa%7D%20%5Cin%20%5C%7B%200%2C%201%20%5C%7D%24%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%82%92%E4%B8%A6%E3%81%B9%E3%81%9F%E6%99%82%E3%81%AE%E9%A0%86%E7%95%AA%E3%81%8C%20%24%5Ckappa%24%20%E7%95%AA%E7%9B%AE%E3%81%A7%E3%81%82%E3%82%8B%E3%81%A8%E3%81%8D%20%241%24.%0A%20%20%20%20%20%20%20%20-%20%24s_%7Bi%20%5Ckappa%7D%24%3A%20%E3%83%9E%E3%82%B7%E3%83%B3%20%24i%24%20%E3%81%AE%20%24%5Ckappa%24%20%E7%95%AA%E7%9B%AE%E3%81%AB%E4%B8%A6%E3%81%B9%E3%82%89%E3%82%8C%E3%81%A6%E3%81%84%E3%82%8B%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E9%96%8B%E5%A7%8B%E6%99%82%E5%88%BB%0A%20%20%20%20%20%20%20%20-%20%24f_%7Bi%20%5Ckappa%7D%24%3A%20%E3%83%9E%E3%82%B7%E3%83%B3%20%24i%24%20%E3%81%AE%20%24%5Ckappa%24%20%E7%95%AA%E7%9B%AE%E3%81%AB%E4%B8%A6%E3%81%B9%E3%82%89%E3%82%8C%E3%81%A6%E3%81%84%E3%82%8B%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E7%B5%82%E4%BA%86%E6%99%82%E5%88%BB%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%5Cbegin%7Balign*%7D%0A%20%20%20%20%20%20%20%20%26%5Ctext%7Bminimize%7D%20%26f_%7Bmn%7D%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%5Ctext%7Bs.t.%7D%20%26%5Csum_%7B%5Ckappa%7D%20x_%7Bj%20%5Ckappa%7D%20%26%3D%201%20%5C%20%26(%5Cforall%20j%20%5Cin%20J)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26%5Csum_%7Bj%20%5Cin%20J%7D%20x_%7Bj%20%5Ckappa%7D%20%26%3D%201%20%5C%20%26(%5Cforall%20%5Ckappa%20%3D%201%2C%20%5Cdots%2C%20n)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26f_%7Bi%20%5Ckappa%7D%20%26%5Cleq%20s_%7Bi%2C%5Ckappa%2B1%7D%20%5C%20%26(%5Cforall%20i%20%5Cin%20M%2C%20%5Cforall%20%5Ckappa%20%3D%201%2C%20%5Cdots%2C%20n-1)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26s_%7Bi%20%5Ckappa%7D%20%2B%20%5Csum_%7Bj%20%5Cin%20J%7D%20p_%7Bij%7D%20x_%7Bj%20%5Ckappa%7D%20%26%5Cleq%20f_%7Bi%20%5Ckappa%7D%20%5C%20%26(%5Cforall%20i%20%5Cin%20M%2C%20%5Cforall%20%5Ckappa%20%3D%201%2C%20%5Cdots%2C%20n)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26f_%7Bi%20%5Ckappa%7D%20%26%5Cleq%20s_%7Bi%2B1%2C%20%5Ckappa%7D%20%5C%20%26(%5Cforall%20i%20%5Cin%20M%20%5Csetminus%20%5C%7Bm%5C%7D%2C%20%5Cforall%20%5Ckappa%20%3D%201%2C%20%5Cdots%2C%20n)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26x_%7Bj%20%5Ckappa%7D%20%26%5Cin%20%5C%7B%200%2C%201%20%5C%7D%20%5C%20%26(%5Cforall%20j%20%5Cin%20J%2C%20%5Ckappa%20%3D%201%2C%20%5Cdots%2C%20n)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26s_%7Bi%20%5Ckappa%7D%20%26%5Cgeq%200%20%5C%20%26(%5Cforall%20i%20%5Cin%20M%2C%20%5Ckappa%20%3D%201%2C%20%5Cdots%2C%20n)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26f_%7Bi%20%5Ckappa%7D%20%26%5Cgeq%200%20%5C%20%26(%5Cforall%20i%20%5Cin%20M%2C%20%5Ckappa%20%3D%201%2C%20%5Cdots%2C%20n)%20%5C%5C%0A%20%20%20%20%20%20%20%20%5Cend%7Balign*%7D%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%23%20%E5%AE%9F%E8%A3%85%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(random)%3A%0A%20%20%20%20def%20make_data_permutation_flow_shop(n%2C%20m)%3A%0A%20%20%20%20%20%20%20%20%22%22%22make_data%3A%20prepare%20matrix%20of%20m%20times%20n%20random%20processing%20times%22%22%22%0A%20%20%20%20%20%20%20%20p%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(1%2C%20m%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20range(1%2C%20n%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20p%5Bi%2C%20j%5D%20%3D%20random.randint(1%2C%2010)%0A%20%20%20%20%20%20%20%20return%20p%0A%20%20%20%20return%20(make_data_permutation_flow_shop%2C)%0A%0A%0A%40app.cell%0Adef%20_(scip)%3A%0A%20%20%20%20def%20permutation_flow_shop(n%2C%20m%2C%20p)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%20permutation_flow_shop%20problem%0A%20%20%20%20%20%20%20%20Parameters%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20n%3A%20number%20of%20jobs%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20m%3A%20number%20of%20machines%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20p%5Bi%2Cj%5D%3A%20processing%20time%20of%20job%20i%20on%20machine%20j%0A%20%20%20%20%20%20%20%20Returns%20a%20model%2C%20ready%20to%20be%20solved.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20model%20%3D%20scip.Model(%22permutation%20flow%20shop%22)%0A%20%20%20%20%20%20%20%20x%2C%20s%2C%20f%20%3D%20%7B%7D%2C%20%7B%7D%2C%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(1%2C%20n%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20range(1%2C%20n%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%5Bj%2C%20k%5D%20%3D%20model.addVar(vtype%3D%22B%22%2C%20name%3D%22x(%25s%2C%25s)%22%20%25%20(j%2C%20k))%0A%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(1%2C%20m%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20range(1%2C%20n%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s%5Bi%2C%20k%5D%20%3D%20model.addVar(vtype%3D%22C%22%2C%20name%3D%22start(%25s%2C%25s)%22%20%25%20(i%2C%20k))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%5Bi%2C%20k%5D%20%3D%20model.addVar(vtype%3D%22C%22%2C%20name%3D%22finish(%25s%2C%25s)%22%20%25%20(i%2C%20k))%0A%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(1%2C%20n%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20model.addCons(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20scip.quicksum(x%5Bj%2C%20k%5D%20for%20k%20in%20range(1%2C%20n%20%2B%201))%20%3D%3D%201%2C%20%22Assign1(%25s)%22%20%25%20(j)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20model.addCons(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20scip.quicksum(x%5Bk%2C%20j%5D%20for%20k%20in%20range(1%2C%20n%20%2B%201))%20%3D%3D%201%2C%20%22Assign2(%25s)%22%20%25%20(j)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(1%2C%20m%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20range(1%2C%20n%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20k%20!%3D%20n%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20model.addCons(f%5Bi%2C%20k%5D%20%3C%3D%20s%5Bi%2C%20k%20%2B%201%5D%2C%20%22FinishStart(%25s%2C%25s)%22%20%25%20(i%2C%20k))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20i%20!%3D%20m%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20model.addCons(f%5Bi%2C%20k%5D%20%3C%3D%20s%5Bi%20%2B%201%2C%20k%5D%2C%20%22Machine(%25s%2C%25s)%22%20%25%20(i%2C%20k))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20model.addCons(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s%5Bi%2C%20k%5D%20%2B%20scip.quicksum(p%5Bi%2C%20j%5D%20*%20x%5Bj%2C%20k%5D%20for%20j%20in%20range(1%2C%20n%20%2B%201))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3D%20f%5Bi%2C%20k%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22StartFinish(%25s%2C%25s)%22%20%25%20(i%2C%20k)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20model.setObjective(f%5Bm%2C%20n%5D%2C%20sense%3D%22minimize%22)%0A%0A%20%20%20%20%20%20%20%20return%20model%2C%20x%2C%20s%2C%20f%0A%20%20%20%20return%20(permutation_flow_shop%2C)%0A%0A%0A%40app.cell%0Adef%20_(make_data_permutation_flow_shop%2C%20permutation_flow_shop)%3A%0A%20%20%20%20n%20%3D%2010%0A%20%20%20%20m%20%3D%2010%0A%20%20%20%20p%20%3D%20make_data_permutation_flow_shop(n%2C%20m)%0A%0A%20%20%20%20model%2C%20x%2C%20s%2C%20f%20%3D%20permutation_flow_shop(n%2C%20m%2C%20p)%0A%20%20%20%20model.optimize()%0A%20%20%20%20print(%22Opt.value%3D%22%2C%20model.getObjVal())%0A%20%20%20%20return%20f%2C%20m%2C%20model%2C%20n%2C%20p%2C%20s%2C%20x%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
9714ce9b97c0203d30f9aa25c050d7afdf6bfc716b8b96be5aecc2a469b0407d