delay

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%201%20%E6%A9%9F%E6%A2%B0%E7%B7%8F%E7%B4%8D%E6%9C%9F%E9%81%85%E3%82%8C%E6%9C%80%E5%B0%8F%E5%8C%96%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(r%22%22%22%23%23%20%E9%9B%A2%E6%8E%A5%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-%20%E6%A9%9F%E6%A2%B0%3A%201%20%E3%81%A4%E3%81%A0%E3%81%91%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%24p_j%24%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%AE%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%0A%20%20%20%20%20%20%20%20-%20%24d_j%24%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%AE%E7%B4%8D%E6%9C%9F%0A%0A%20%20%20%20%20%20%20%20%E5%90%84%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%20%24d_j%24%20%E3%81%8B%E3%82%89%E3%81%AE%E9%81%85%E3%82%8C%E3%81%AE%E9%87%8D%E3%81%BF%E4%BB%98%E3%81%8D%E5%92%8C%E3%82%92%E6%9C%80%E5%B0%8F%E5%8C%96%E3%81%99%E3%82%8B.%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%24M%24%20%E3%82%92%E5%A4%A7%E3%81%8D%E3%81%AA%E5%AE%9A%E6%95%B0%E3%81%A8%E3%81%97%E3%81%A6%0A%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%26%5Csum_%7Bj%20%5Cin%20J%7D%20w_j%20T_j%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%5Ctext%7Bs.t.%7D%20%26x_%7Bjk%7D%20%2B%20x_%7Bkj%7D%20%26%3D%201%20%5C%20%26(%5Cforall%20j%20%3C%20k)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26x_%7Bjk%7D%20%2B%20x_%7Bkl%7D%20%2B%20x_%7Blj%7D%20%26%5Cleq%202%20%5C%20%26(%5Cforall%20j%20%5Cneq%20k%20%5Cneq%20l)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26%5Csum_%7Bk%20%5Cneq%20j%7D%20p_k%20x_%7Bkj%7D%20%2Bp_j%20%26%5Cleq%20d_j%20%2B%20T_j%20%20%5C%20%26(%5Cforall%20j%20%5Cin%20J)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26x_%7Bjk%7D%20%26%5Cin%20%5C%7B%200%2C%201%20%5C%7D%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(n)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Data%20generator%20for%20the%20one%20machine%20scheduling%20problem.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20p%2C%20r%2C%20d%2C%20w%20%3D%20%7B%7D%2C%20%7B%7D%2C%20%7B%7D%2C%20%7B%7D%0A%0A%20%20%20%20%20%20%20%20J%20%3D%20range(1%2C%20n%20%2B%201)%0A%0A%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20p%5Bj%5D%20%3D%20random.randint(1%2C%204)%0A%20%20%20%20%20%20%20%20%20%20%20%20w%5Bj%5D%20%3D%20random.randint(1%2C%203)%0A%0A%20%20%20%20%20%20%20%20T%20%3D%20sum(p)%0A%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20r%5Bj%5D%20%3D%20random.randint(0%2C%205)%0A%20%20%20%20%20%20%20%20%20%20%20%20d%5Bj%5D%20%3D%20r%5Bj%5D%20%2B%20random.randint(0%2C%205)%0A%0A%20%20%20%20%20%20%20%20return%20J%2C%20p%2C%20r%2C%20d%2C%20w%0A%20%20%20%20return%20(make_data%2C)%0A%0A%0A%40app.cell%0Adef%20_(scip)%3A%0A%20%20%20%20def%20scheduling_linear_ordering(J%2C%20p%2C%20d%2C%20w)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20scheduling_linear_ordering%3A%20model%20for%20the%20one%20machine%20total%20weighted%20tardiness%20problem%0A%0A%20%20%20%20%20%20%20%20Model%20for%20the%20one%20machine%20total%20weighted%20tardiness%20problem%0A%20%20%20%20%20%20%20%20using%20the%20linear%20ordering%20formulation%0A%0A%20%20%20%20%20%20%20%20Parameters%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20J%3A%20set%20of%20jobs%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20p%5Bj%5D%3A%20processing%20time%20of%20job%20j%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20d%5Bj%5D%3A%20latest%20non-tardy%20time%20for%20job%20j%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20w%5Bj%5D%3A%20weighted%20of%20job%20j%2C%20%20the%20objective%20is%20the%20sum%20of%20the%20weighted%20completion%20time%0A%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(%22scheduling%3A%20linear%20ordering%22)%0A%0A%20%20%20%20%20%20%20%20T%2C%20x%20%3D%20%7B%7D%2C%20%7B%7D%20%20%23%20tardiness%20variable%2C%20%20x%5Bj%2Ck%5D%20%3D1%20if%20job%20j%20precedes%20job%20k%2C%20%3D0%20otherwise%0A%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20T%5Bj%5D%20%3D%20model.addVar(vtype%3D%22C%22%2C%20name%3D%22T(%25s)%22%20%25%20(j))%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20!%3D%20k%3A%0A%20%20%20%20%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%20j%20in%20J%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(p%5Bk%5D%20*%20x%5Bk%2C%20j%5D%20for%20k%20in%20J%20if%20k%20!%3D%20j)%20-%20T%5Bj%5D%20%3C%3D%20d%5Bj%5D%20-%20p%5Bj%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Tardiness(%25r)%22%20%25%20(j)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20k%20%3C%3D%20j%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20model.addCons(x%5Bj%2C%20k%5D%20%2B%20x%5Bk%2C%20j%5D%20%3D%3D%201%2C%20%22Disjunctive(%25s%2C%25s)%22%20%25%20(j%2C%20k))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20ell%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20ell%20%3D%3D%20j%20or%20ell%20%3D%3D%20k%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20if%20ell%20%3E%20k%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20j%20%3C%20k%20%3C%20ell%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%201%20-%3E%203%20-%3E%202%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20x%5B1%2C%203%5D%2C%20x%5B3%2C%202%5D%2C%20x%5B2%2C%201%5D%0A%20%20%20%20%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%20%20%20%20%20x%5Bj%2C%20k%5D%20%2B%20x%5Bk%2C%20ell%5D%20%2B%20x%5Bell%2C%20j%5D%20%3C%3D%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Triangle(%25s%2C%25s%2C%25s)%22%20%25%20(j%2C%20k%2C%20ell)%2C%0A%20%20%20%20%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(scip.quicksum(w%5Bj%5D%20*%20T%5Bj%5D%20for%20j%20in%20J)%2C%20sense%3D%22minimize%22)%0A%0A%20%20%20%20%20%20%20%20return%20model%2C%20x%2C%20T%0A%20%20%20%20return%20(scheduling_linear_ordering%2C)%0A%0A%0A%40app.cell%0Adef%20_(make_data%2C%20scheduling_linear_ordering)%3A%0A%20%20%20%20n%20%3D%205%20%20%23%20number%20of%20jobs%0A%20%20%20%20J%2C%20p%2C%20r%2C%20d%2C%20w%20%3D%20make_data(n)%0A%0A%20%20%20%20model%2C%20x%2C%20T%20%3D%20scheduling_linear_ordering(J%2C%20p%2C%20d%2C%20w)%0A%20%20%20%20model.optimize()%0A%20%20%20%20z%20%3D%20model.getObjVal()%0A%20%20%20%20for%20(i%2C%20j)%20in%20x%3A%0A%20%20%20%20%20%20%20%20if%20model.getVal(x%5Bi%2C%20j%5D)%20%3E%200.5%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print(%22x(%25s)%20%3D%20%25s%22%20%25%20((i%2C%20j)%2C%20int(model.getVal(x%5Bi%2C%20j%5D)%20%2B%200.5)))%0A%20%20%20%20for%20i%20in%20T%3A%0A%20%20%20%20%20%20%20%20print(%22T(%25s)%20%3D%20%25s%22%20%25%20(i%2C%20int(model.getVal(T%5Bi%5D)%20%2B%200.5)))%0A%20%20%20%20print(%22Opt.value%20by%20the%20linear%20ordering%20formulation%3D%22%2C%20z)%0A%20%20%20%20return%20J%2C%20T%2C%20d%2C%20i%2C%20j%2C%20model%2C%20n%2C%20p%2C%20r%2C%20w%2C%20x%2C%20z%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A