import%20marimo%0A%0A__generated_with%20%3D%20%220.12.4%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%20os%0A%20%20%20%20from%20typing%20import%20Self%0A%20%20%20%20from%20pathlib%20import%20Path%0A%20%20%20%20import%20pydantic%0A%20%20%20%20import%20highspy%0A%20%20%20%20from%20ortools.sat.python%20import%20cp_model%0A%20%20%20%20return%20Path%2C%20Self%2C%20cp_model%2C%20highspy%2C%20os%2C%20pydantic%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%20%E8%B3%87%E6%BA%90%E5%88%B6%E7%B4%84%E4%BB%98%E3%81%8D%E3%83%97%E3%83%AD%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%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%23%23%23%20%E5%85%A5%E5%8A%9B%E3%83%87%E3%83%BC%E3%82%BF%0A%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E9%9B%86%E5%90%88%20%24%5Cmathrm%7BJob%7D%24%2C%20%E6%B7%BB%E5%AD%97%E3%81%AF%20%24j%2C%20k%24%0A%20%20%20%20%20%20%20%20-%20%E8%B3%87%E6%BA%90%E3%81%AE%E9%9B%86%E5%90%88%20%24%5Cmathrm%7BRes%7D%24%2C%20%E6%B7%BB%E5%AD%97%E3%81%AF%20%24r%24%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%E9%96%93%E3%81%AE%E6%99%82%E9%96%93%E6%88%90%E7%B4%84%E3%82%92%E8%A1%A8%E3%81%99%E9%9B%86%E5%90%88%20%24%5Cmathrm%7BPrec%7D%20%5Csubset%20%5Cmathrm%7BJob%7D%20%5Ctimes%20%5Cmathrm%7BJob%7D%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24(j%2Ck)%20%5Cin%20%5Cmathrm%7BPrec%7D%24%20%E3%81%AE%E3%81%A8%E3%81%8D%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%A8%E3%82%B8%E3%83%A7%E3%83%96%20%24k%24%20%E3%81%AE%E6%99%82%E5%88%BB%E9%96%93%E3%81%AB%E4%BD%95%E3%81%8B%E3%81%97%E3%82%89%E3%81%AE%E9%96%A2%E4%BF%82%E3%81%8C%E3%81%82%E3%82%8B.%20%0A%20%20%20%20%20%20%20%20-%20%E6%9C%80%E5%A4%A7%E3%81%AE%E6%9C%9F%E6%95%B0%20%24T%24%2C%20%E6%B7%BB%E5%AD%97%E3%81%AF%20%24t%2C%20s%20%5Cin%20%5C%7B1%2C%20%5Cdots%2C%20T%20%5C%7D%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%E6%9C%9F%E9%96%93%20%24t%24%20%E3%81%AF%E6%99%82%E5%88%BB%20%24t-1%24%20%E3%81%8B%E3%82%89%E6%99%82%E5%88%BB%20%24t%24%20%E3%81%BE%E3%81%A7%E3%81%A7%E3%81%82%E3%82%8B%E3%81%A8%E3%81%99%E3%82%8B.%20%0A%20%20%20%20%20%20%20%20-%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%20%24p_j%24%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%82%92%E6%9C%9F%20%24t%24%20%E3%81%AB%E9%96%8B%E5%A7%8B%E3%81%97%E3%81%9F%E3%81%A8%E3%81%8D%E3%81%AE%E8%B2%BB%E7%94%A8%20%24%5Cmathrm%7BCost%7D_%7Bjt%7D%24%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%AE%E9%96%8B%E5%A7%8B%E5%BE%8C%20%24t%24%20%E6%9C%9F%E7%B5%8C%E9%81%8E%E6%99%82%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AB%E8%A6%81%E3%81%99%E3%82%8B%E8%B3%87%E6%BA%90%20%24r%24%20%E3%81%AE%E9%87%8F%20%24a_%7Bjrt%7D%24%0A%20%20%20%20%20%20%20%20-%20%E6%9C%9F%20%24t%24%20%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E8%B3%87%E6%BA%90%20%24r%24%20%E3%81%AE%E4%BD%BF%E7%94%A8%E5%8F%AF%E8%83%BD%E9%87%8F%E4%B8%8A%E9%99%90%20%24%5Cmathrm%7BRUB%7D_%7Brt%7D%24%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%23%23%23%20%E5%A4%89%E6%95%B0%0A%0A%20%20%20%20%20%20%20%20-%20%24x_%7Bjt%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%E6%9C%9F%20%24t%24%20%E3%81%AB%E9%96%8B%E5%A7%8B%E3%81%99%E3%82%8B%E3%81%A8%E3%81%8D%20%241%24%2C%20%E3%81%9D%E3%82%8C%E4%BB%A5%E5%A4%96%E3%81%AF%20%240%24%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%23%23%23%20%E7%9B%AE%E7%9A%84%E9%96%A2%E6%95%B0%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cmin%20%5Csum_%7Bj%20%5Cin%20%5Cmathrm%7BJob%7D%7D%20%5Csum_%7Bt%3D1%7D%5E%7BT-p_j%2B1%7D%20%5Cmathrm%7BCost%7D_%7Bjt%7D%20x_%7Bjt%7D%0A%20%20%20%20%20%20%20%20%24%24%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%23%23%23%20%E5%88%B6%E7%B4%84%E6%9D%A1%E4%BB%B6%0A%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%E9%81%82%E8%A1%8C%E6%88%90%E7%B4%84%3A%0A%20%20%20%20%20%20%20%20%20%20%24%5Csum_%7Bt%3D1%7D%5E%7BT-p_j%2B1%7D%20x_%7Bjt%7D%20%3D%201%20%5Cquad%20(%5Cforall%20j%20%5Cin%20%5Cmathrm%7BJob%7D)%24%0A%20%20%20%20%20%20%20%20-%20%E8%B3%87%E6%BA%90%E6%88%90%E7%B4%84%3A%0A%20%20%20%20%20%20%20%20%20%20%24%5Csum_%7Bj%20%5Cin%20%5Cmathrm%7BJob%7D%7D%20%5Csum_%7Bs%20%3D%20%5Cmax(t%20-%20p_j%20%2B%201%2C%201)%7D%5E%7B%5Cmin(t%2C%20T%20-%20p_j%20%2B%201)%7D%20a_%7Bjr%2Ct-s%7D%20x_%7Bjs%7D%20%5Cleq%20%5Cmathrm%7BRUB%7D_%7Brt%7D%20%5Cquad%20(%5Cforall%20r%20%5Cin%20%5Cmathrm%7BRes%7D%2C%20%5Cforall%20t%20%5Cin%20%5C%7B%201%2C%20%5Cdots%2C%20T%20%5C%7D)%24%0A%20%20%20%20%20%20%20%20-%20%E6%99%82%E9%96%93%E5%88%B6%E7%B4%84%3A%20%24%5Csum_%7Bt%3D2%7D%5E%7BT-p_j%2B1%7D%20(t-1)x_%7Bjt%7D%20%2B%20p_j%20%5Cleq%20%5Csum_%7Bt%3D2%7D%5E%7BT-p_k%2B1%7D%20(t-1)%20x_%7Bkt%7D%20%5Cquad%20(%5Cforall%20(j%2Ck)%20%5Cin%20%5Cmathrm%7BPrec%7D)%24%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%0Adef%20multidict()%3A%0A%20%20%20%20%23%20https%3A%2F%2Fscmopt.github.io%2Fmanual%2F15mypulp.html%23multidict%25E9%2596%25A2%25E6%2595%25B0%0A%0A%20%20%20%20def%20multidict(d%3A%20dict)%3A%0A%20%20%20%20%20%20%20%20ret%20%3D%20%5Blist(d.keys())%5D%0A%20%20%20%20%20%20%20%20for%20k%2C%20arr%20in%20d.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20type(arr)%20is%20not%20list%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%20%3D%20%5Barr%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20append_num%20%3D%201%20%2B%20len(arr)%20-%20len(ret)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20append_num%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ret%20%3D%20ret%20%2B%20%5B%7B%7D%20for%20_%20in%20range(append_num)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%2C%20val%20in%20enumerate(arr)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ret%5Bi%20%2B%201%5D%5Bk%5D%20%3D%20val%0A%20%20%20%20%20%20%20%20return%20ret%0A%20%20%20%20return%20(multidict%2C)%0A%0A%0A%40app.cell%0Adef%20make_1r(multidict)%3A%0A%20%20%20%20def%20make_1r()%3A%0A%20%20%20%20%20%20%20%20J%2C%20p%20%3D%20multidict(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%20%20%23%20jobs%2C%20processing%20times%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%202%3A%203%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%203%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%204%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20P%20%3D%20%5B(1%2C%202)%2C%20(1%2C%203)%2C%20(2%2C%204)%5D%0A%20%20%20%20%20%20%20%20R%20%3D%20%5B1%5D%0A%20%20%20%20%20%20%20%20T%20%3D%206%0A%20%20%20%20%20%20%20%20c%20%3D%20%7B%7D%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%20for%20t%20in%20range(1%2C%20T%20-%20p%5Bj%5D%20%2B%202)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20c%5Bj%2C%20t%5D%20%3D%201%20*%20(t%20-%201%20%2B%20p%5Bj%5D)%0A%20%20%20%20%20%20%20%20a%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%201%2C%200)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%201%2C%200)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%201%2C%201)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%201%2C%202)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(3%2C%201%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(3%2C%201%2C%201)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(4%2C%201%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(4%2C%201%2C%201)%3A%202%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20RUB%20%3D%20%7B(1%2C%201)%3A%202%2C%20(1%2C%202)%3A%202%2C%20(1%2C%203)%3A%201%2C%20(1%2C%204)%3A%202%2C%20(1%2C%205)%3A%202%2C%20(1%2C%206)%3A%202%7D%0A%20%20%20%20%20%20%20%20return%20(J%2C%20P%2C%20R%2C%20T%2C%20p%2C%20c%2C%20a%2C%20RUB)%0A%20%20%20%20return%20(make_1r%2C)%0A%0A%0A%40app.cell%0Adef%20make_2r(multidict)%3A%0A%20%20%20%20def%20make_2r()%3A%0A%20%20%20%20%20%20%20%20J%2C%20p%20%3D%20multidict(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%20%20%23%20jobs%2C%20processing%20times%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%202%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%203%3A%203%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%204%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%205%3A%205%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20P%20%3D%20%5B(1%2C%202)%2C%20(1%2C%203)%2C%20(2%2C%204)%5D%0A%20%20%20%20%20%20%20%20R%20%3D%20%5B1%2C%202%5D%0A%20%20%20%20%20%20%20%20T%20%3D%206%0A%20%20%20%20%20%20%20%20c%20%3D%20%7B%7D%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%20for%20t%20in%20range(1%2C%20T%20-%20p%5Bj%5D%20%2B%202)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20c%5Bj%2C%20t%5D%20%3D%201%20*%20(t%20-%201%20%2B%20p%5Bj%5D)%0A%20%20%20%20%20%20%20%20a%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20resource%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%201%2C%200)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%201%2C%201)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%201%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%201%2C%201)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(3%2C%201%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(3%2C%201%2C%201)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(3%2C%201%2C%202)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(4%2C%201%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(4%2C%201%2C%201)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%201%2C%200)%3A%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%201%2C%201)%3A%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%201%2C%202)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%201%2C%203)%3A%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%201%2C%204)%3A%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20resource%202%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%202%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%202%2C%201)%3A%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%202%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%202%2C%201)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(3%2C%202%2C%200)%3A%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(3%2C%202%2C%201)%3A%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(3%2C%202%2C%202)%3A%200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(4%2C%202%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(4%2C%202%2C%201)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%202%2C%200)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%202%2C%201)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%202%2C%202)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%202%2C%203)%3A%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(5%2C%202%2C%204)%3A%201%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20RUB%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%201)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%202)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%203)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%204)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%205)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%206)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(1%2C%207)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%201)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%202)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%203)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%204)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%205)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%206)%3A%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(2%2C%207)%3A%202%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20(J%2C%20P%2C%20R%2C%20T%2C%20p%2C%20c%2C%20a%2C%20RUB)%0A%20%20%20%20return%20(make_2r%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%23%20HiGHS%20%E3%81%AB%E3%82%88%E3%82%8B%E3%83%A2%E3%83%87%E3%83%AA%E3%83%B3%E3%82%B0%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(highspy)%3A%0A%20%20%20%20class%20Model1Highs%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20J%2C%20P%2C%20R%2C%20T%2C%20p%2C%20c%2C%20a%2C%20RUB)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model%20%3D%20highspy.Highs()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20s%20-%20start%20time%20variable%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20x%3D1%20if%20job%20j%20starts%20on%20period%20t%0A%20%20%20%20%20%20%20%20%20%20%20%20self.s%2C%20self.x%20%3D%20%7B%7D%2C%20%7B%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.s%5Bj%5D%20%3D%20self.model.addVariable()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20t%20in%20range(1%2C%20T%20-%20p%5Bj%5D%20%2B%202)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.x%5Bj%2C%20t%5D%20%3D%20self.model.addBinary()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20job%20execution%20constraints%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum(self.x%5Bj%2C%20t%5D%20for%20t%20in%20range(1%2C%20T%20-%20p%5Bj%5D%20%2B%202))%20%3D%3D%201%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%20%20%20%20%20%20%20%20%20%23%20start%20time%20constraints%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum((t%20-%201)%20*%20self.x%5Bj%2C%20t%5D%20for%20t%20in%20range(2%2C%20T%20-%20p%5Bj%5D%20%2B%202))%20%3D%3D%20self.s%5Bj%5D%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%20%20%20%20%20%23%20resource%20upper%20bound%20constraints%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20t%20in%20range(1%2C%20T%2B1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20r%20in%20R%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum(%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%20%20%20%20a%5Bj%2C%20r%2C%20t%20-%20t_%5D%20*%20self.x%5Bj%2C%20t_%5D%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%20%20%20%20for%20j%20in%20J%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%20%20%20%20for%20t_%20in%20range(max(t%20-%20p%5Bj%5D%20%2B%201%2C%201)%2C%20min(t%20%2B%201%2C%20T%20-%20p%5Bj%5D%20%2B%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)%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%3C%3D%20RUB%5Br%2C%20t%5D%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%20%20%20%20%20%23%20time%20(precedence)%20constraints%2C%20i.e.%2C%20s%5Bk%5D-s%5Bj%5D%20%3E%3D%20p%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(j%2C%20k)%20in%20P%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(self.s%5Bk%5D%20-%20self.s%5Bj%5D%20%3E%3D%20p%5Bj%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.objective%20%3D%20sum(c%5Bj%2C%20t%5D%20*%20self.x%5Bj%2C%20t%5D%20for%20(j%2C%20t)%20in%20self.x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20self.model.minimize(self.objective)%0A%0A%20%20%20%20%20%20%20%20def%20solve(self)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20self.model.run()%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model.minimize(self.objective)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solution%20%3D%20self.model.getSolution()%0A%20%20%20%20%20%20%20%20%20%20%20%20self.info%20%3D%20self.model.getInfo()%0A%20%20%20%20return%20(Model1Highs%2C)%0A%0A%0A%40app.cell%0Adef%20_(Model1Highs%2C%20make_1r)%3A%0A%20%20%20%20(J1%2C%20P1%2C%20R1%2C%20T1%2C%20p1%2C%20c1%2C%20a1%2C%20RUB1)%20%3D%20make_1r()%0A%20%20%20%20model1%20%3D%20Model1Highs(J1%2C%20P1%2C%20R1%2C%20T1%2C%20p1%2C%20c1%2C%20a1%2C%20RUB1)%0A%0A%20%20%20%20model1.solve()%0A%20%20%20%20return%20J1%2C%20P1%2C%20R1%2C%20RUB1%2C%20T1%2C%20a1%2C%20c1%2C%20model1%2C%20p1%0A%0A%0A%40app.cell%0Adef%20_(model1)%3A%0A%20%20%20%20print%20(f%22Opt.value%20%3D%20%7Bmodel1.info.objective_function_value%7D%22)%0A%0A%20%20%20%20for%20(_j%2C%20_t)%20in%20model1.x%3A%0A%20%20%20%20%20%20%20%20_val%20%3D%20model1.solution.col_value%5Bmodel1.x%5B_j%2C%20_t%5D.index%5D%0A%20%20%20%20%20%20%20%20if%20_val%20%3E%200.5%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print(f%22x%5B%7B_j%7D%2C%7B_t%7D%5D%20%3D%20%7B_val%7D%22)%0A%0A%20%20%20%20for%20_j%20in%20model1.s%3A%0A%20%20%20%20%20%20%20%20_val%20%3D%20model1.solution.col_value%5Bmodel1.s%5B_j%5D.index%5D%0A%20%20%20%20%20%20%20%20print(f%22s%5B%7B_j%7D%5D%20%3D%20%7B_val%7D%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Model1Highs%2C%20make_2r)%3A%0A%20%20%20%20(J2%2C%20P2%2C%20R2%2C%20T2%2C%20p2%2C%20c2%2C%20a2%2C%20RUB2)%20%3D%20make_2r()%0A%20%20%20%20model2%20%3D%20Model1Highs(J2%2C%20P2%2C%20R2%2C%20T2%2C%20p2%2C%20c2%2C%20a2%2C%20RUB2)%0A%0A%20%20%20%20model2.solve()%0A%20%20%20%20return%20J2%2C%20P2%2C%20R2%2C%20RUB2%2C%20T2%2C%20a2%2C%20c2%2C%20model2%2C%20p2%0A%0A%0A%40app.cell%0Adef%20_(model2)%3A%0A%20%20%20%20print%20(f%22Opt.value%20%3D%20%7Bmodel2.info.objective_function_value%7D%22)%0A%0A%20%20%20%20for%20(_j%2C%20_t)%20in%20model2.x%3A%0A%20%20%20%20%20%20%20%20_val%20%3D%20model2.solution.col_value%5Bmodel2.x%5B_j%2C%20_t%5D.index%5D%0A%20%20%20%20%20%20%20%20if%20_val%20%3E%200.5%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print(f%22x%5B%7B_j%7D%2C%7B_t%7D%5D%20%3D%20%7B_val%7D%22)%0A%0A%20%20%20%20for%20_j%20in%20model2.s%3A%0A%20%20%20%20%20%20%20%20_val%20%3D%20model2.solution.col_value%5Bmodel2.s%5B_j%5D.index%5D%0A%20%20%20%20%20%20%20%20print(f%22s%5B%7B_j%7D%5D%20%3D%20%7B_val%7D%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%E3%82%A4%E3%83%B3%E3%82%B9%E3%82%BF%E3%83%B3%E3%82%B9%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%23%20kobe-scheduling%0A%0A%20%20%20%20%20%20%20%20-%20%E3%83%AA%E3%83%B3%E3%82%AF%3A%20https%3A%2F%2Fgithub.com%2Fptal%2Fkobe-scheduling%0A%20%20%20%20%20%20%20%20-%20%E3%83%87%E3%83%BC%E3%82%BF%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%83%E3%83%88%E3%81%AF%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AB%E3%82%88%E3%81%A3%E3%81%A6%E7%95%B0%E3%81%AA%E3%82%8A%2C%20%E7%89%B9%E3%81%AB%E8%AA%AC%E6%98%8E%E3%82%82%E3%81%AA%E3%81%84.%20%0A%20%20%20%20%20%20%20%20%20%20https%3A%2F%2Fgithub.com%2Fptal%2Fkobe-scheduling%2Fdata%2Frcpsp%2Fpatterson.rcp%20%E3%81%A7%E3%81%82%E3%82%8C%E3%81%B0%20(%E5%A4%9A%E5%88%86)%0A%20%20%20%20%20%20%20%20%20%20%20%20-%201%20%E8%A1%8C%E7%9B%AE%3A%20%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E6%95%B0%2C%20%E3%83%AA%E3%82%BD%E3%83%BC%E3%82%B9%E3%81%AE%E7%A8%AE%E9%A1%9E%0A%20%20%20%20%20%20%20%20%20%20%20%20-%203%20%E8%A1%8C%E7%9B%AE%3A%20%E5%90%84%E3%83%AA%E3%82%BD%E3%83%BC%E3%82%B9%E3%81%AE%E4%B8%8A%E9%99%90%E5%80%A4%0A%20%20%20%20%20%20%20%20%20%20%20%20-%205%20%E8%A1%8C%E7%9B%AE%E4%BB%A5%E9%99%8D%3A%20%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E6%83%85%E5%A0%B1%E3%81%8C%E4%B8%A6%E3%81%B6.%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%2C%20%5B%E3%83%AA%E3%82%BD%E3%83%BC%E3%82%B9%E3%81%AE%E6%B6%88%E8%B2%BB%E6%95%B0%2C%20...%5D%2C%20%E5%BE%8C%E7%B6%9A%E3%82%B8%E3%83%A7%E3%83%96%E6%95%B0%2C%20%5B%E5%BE%8C%E7%B6%9A%E3%82%B8%E3%83%A7%E3%83%96%E7%95%AA%E5%8F%B7%2C%20...%5D%0A%20%20%20%20%20%20%20%20-%20%E7%9B%AE%E7%9A%84%E9%96%A2%E6%95%B0%E3%81%AF%20makespan%20(%E5%A4%9A%E5%88%86)%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%0Adef%20_(Path%2C%20__file__%2C%20os)%3A%0A%20%20%20%20parent%20%3D%20str(Path(os.path.abspath(__file__)).parent)%0A%20%20%20%20data_dir%20%3D%20Path(parent%2C%20%22kobe-scheduling%22%2C%20%22data%22%2C%20%22rcpsp%22%2C%20%22patterson.rcp%22)%0A%20%20%20%20return%20data_dir%2C%20parent%0A%0A%0A%40app.cell%0Adef%20_(Self%2C%20pydantic)%3A%0A%20%20%20%20class%20Job(pydantic.BaseModel)%3A%0A%20%20%20%20%20%20%20%20model_config%20%3D%20pydantic.ConfigDict(frozen%3DTrue)%0A%20%20%20%20%20%20%20%20id%3A%20int%0A%20%20%20%20%20%20%20%20time%3A%20int%0A%20%20%20%20%20%20%20%20res_usages%3A%20list%5Bint%5D%0A%0A%20%20%20%20class%20Resource(pydantic.BaseModel)%3A%0A%20%20%20%20%20%20%20%20model_config%20%3D%20pydantic.ConfigDict(frozen%3DTrue)%0A%20%20%20%20%20%20%20%20ub%3A%20int%0A%0A%20%20%20%20class%20Condition(pydantic.BaseModel)%3A%0A%20%20%20%20%20%20%20%20model_config%20%3D%20pydantic.ConfigDict(frozen%3DTrue)%0A%20%20%20%20%20%20%20%20jobs%3A%20list%5BJob%5D%0A%20%20%20%20%20%20%20%20ress%3A%20list%5BResource%5D%0A%20%20%20%20%20%20%20%20prec%3A%20set%5Btuple%5Bint%2Cint%5D%5D%0A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20from_file(filepath)%20-%3E%20Self%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prec%20%3D%20set()%0A%20%20%20%20%20%20%20%20%20%20%20%20with%20open(filepath)%20as%20f%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_njobs%2C%20_nress%20%3D%20map(lambda%20s%3A%20int(s)%2C%20f.readline().split())%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f.readline()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20resubs%20%3D%20list(map(lambda%20s%3A%20int(s)%2C%20f.readline().split()))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ress%20%3D%20%5BResource(ub%3Dresub)%20for%20resub%20in%20resubs%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20jobs%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20job_id%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(line%20%3A%3D%20f.readline())%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20datas%20%3D%20list(map(lambda%20s%3A%20int(s)%2C%20line.split()))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20len(datas)%20%3D%3D%200%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%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idx%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20time%20%3D%20datas%5Bidx%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idx%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res_usages%20%3D%20%5Bdatas%5Bidx%20%2B%20jdx%5D%20for%20jdx%20in%20range(_nress)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idx%20%2B%3D%20_nress%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20%E6%AC%A1%E3%81%8B%E3%82%89%E5%A7%8B%E3%81%BE%E3%82%8B%E6%95%B0%E5%80%A4%E5%88%97%E3%81%AE%E9%95%B7%E3%81%95%E3%81%AA%E3%81%AE%E3%81%A7%E3%82%B9%E3%82%AD%E3%83%83%E3%83%97%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idx%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20idx%20%3C%20len(datas)%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%20prec.add((job_id%2C%20datas%5Bidx%5D%20-%201))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idx%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20jobs.append(Job(id%3Djob_id%2C%20time%3Dtime%2C%20res_usages%3Dres_usages))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20job_id%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20Condition(jobs%3Djobs%2C%20ress%3Dress%2C%20prec%3Dprec)%0A%20%20%20%20return%20Condition%2C%20Job%2C%20Resource%0A%0A%0A%40app.cell%0Adef%20_(Condition%2C%20Path%2C%20data_dir)%3A%0A%20%20%20%20_filepath%20%3D%20data_dir%20%2F%20Path(%22pat1.rcp%22)%0A%20%20%20%20cond1%20%3D%20Condition.from_file(_filepath)%0A%20%20%20%20return%20(cond1%2C)%0A%0A%0A%40app.cell%0Adef%20_(cond1)%3A%0A%20%20%20%20cond1.model_dump()%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Condition%2C%20highspy)%3A%0A%20%20%20%20class%20Model2Highs%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20cond%3A%20Condition)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model%20%3D%20highspy.Highs()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20horizon%20%3D%20sum(job.time%20for%20job%20in%20cond.jobs)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20s%5Bj%5D%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20j%20%E3%81%AE%E9%96%8B%E5%A7%8B%E6%9C%9F%0A%20%20%20%20%20%20%20%20%20%20%20%20self.s%20%3D%20%5Bself.model.addVariable(ub%3Dhorizon%20-%201)%20for%20job%20in%20cond.jobs%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20e%5Bj%5D%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20j%20%E3%81%AE%E7%B5%82%E4%BA%86%E6%9C%9F%20%22%E3%81%AE%E6%AC%A1%E3%81%AE%E6%9C%9F%22%0A%20%20%20%20%20%20%20%20%20%20%20%20self.e%20%3D%20%5Bself.s%5Bjdx%5D%20%2B%20job.time%20for%20jdx%2C%20job%20in%20enumerate(cond.jobs)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20x%5Bj%5D%5Bt%5D%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20j%20%E3%82%92%E6%9C%9F%20t%20%E3%81%AB%E9%96%8B%E5%A7%8B%E3%81%99%E3%82%8B%E6%99%82%E3%81%A0%E3%81%91%201%0A%20%20%20%20%20%20%20%20%20%20%20%20self.x%20%3D%20%5B%5Bself.model.addBinary()%20for%20t%20in%20range(horizon)%5D%20for%20job%20in%20cond.jobs%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20%E5%90%84%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AF%E5%BF%85%E3%81%9A%E5%87%A6%E7%90%86%E3%81%95%E3%82%8C%E3%82%8B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20jdx%2C%20job%20in%20enumerate(cond.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum(self.x%5Bjdx%5D%5Bt%5D%20for%20t%20in%20range(horizon%20-%20max(0%2C%20job.time%20-%201)))%20%3D%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20t%20in%20range(horizon%20-%20max(0%2C%20job.time%20-%201)%2C%20horizon)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(self.x%5Bjdx%5D%5Bt%5D%20%3D%3D%200)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20s%20%E3%81%A8%20x%20%E3%81%AE%E9%96%A2%E4%BF%82%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstrs(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum(t%20*%20self.x%5Bjdx%5D%5Bt%5D%20for%20t%20in%20range(horizon))%20%3D%3D%20self.s%5Bjdx%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20jdx%2C%20_%20in%20enumerate(cond.jobs)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5D%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%20%23%20%E3%82%B8%E3%83%A7%E3%83%96%E4%BE%9D%E5%AD%98%E9%96%A2%E4%BF%82%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20idx%2C%20jdx%20in%20cond.prec%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(self.e%5Bidx%5D%20%3C%3D%20self.s%5Bjdx%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20%E8%B3%87%E6%BA%90%E5%88%B6%E7%B4%84%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_res%2C%20res%20in%20enumerate(cond.ress)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20t%20in%20range(horizon)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum(%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%20%20%20%20sum(%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%20%20%20%20%20%20%20%20self.x%5Bid_job%5D%5B_t%5D%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%20%20%20%20%20%20%20%20for%20_t%20in%20range(max(0%2C%20t%20-%20job.time%20%2B%201)%2C%20t%20%2B%201)%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%20%20%20%20)%20*%20job.res_usages%5Bid_res%5D%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%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(cond.jobs)%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)%20%3C%3D%20res.ub%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%20%20%20%20%20%23%20%E7%9B%AE%E7%9A%84%E9%96%A2%E6%95%B0%3A%20makespan%0A%20%20%20%20%20%20%20%20%20%20%20%20self.objective%20%3D%20self.model.addVariable(ub%3Dhorizon)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20jdx%2C%20job%20in%20enumerate(cond.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.addConstr(self.objective%20%3E%3D%20self.e%5Bjdx%5D)%0A%0A%20%20%20%20%20%20%20%20def%20solve(self)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20self.model.run()%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model.minimize(self.objective)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solution%20%3D%20self.model.getSolution()%0A%20%20%20%20%20%20%20%20%20%20%20%20self.info%20%3D%20self.model.getInfo()%0A%20%20%20%20return%20(Model2Highs%2C)%0A%0A%0A%40app.cell%0Adef%20_(Model2Highs%2C%20cond1)%3A%0A%20%20%20%20model3%20%3D%20Model2Highs(cond1)%0A%20%20%20%20model3.solve()%0A%20%20%20%20return%20(model3%2C)%0A%0A%0A%40app.cell%0Adef%20_(model3)%3A%0A%20%20%20%20print%20(f%22Opt.value%20%3D%20%7Bmodel3.info.objective_function_value%7D%22)%0A%0A%20%20%20%20for%20_id_job%2C%20s%20in%20enumerate(model3.s)%3A%0A%20%20%20%20%20%20%20%20_val%20%3D%20model3.solution.col_value%5Bs.index%5D%0A%20%20%20%20%20%20%20%20print(f%22s%5B%7B_id_job%7D%5D%20%3D%20%7B_val%7D%22)%0A%20%20%20%20return%20(s%2C)%0A%0A%0A%40app.cell%0Adef%20_(Condition%2C%20cp_model)%3A%0A%20%20%20%20class%20Model2CpSat%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20cond%3A%20Condition)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model%20%3D%20cp_model.CpModel()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20horizon%20%3D%20sum(job.time%20for%20job%20in%20cond.jobs)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.starts%20%3D%20%5Bself.model.new_int_var(lb%3D0%2C%20ub%3Dhorizon-job.time%2C%20name%3D%22%22)%20for%20job%20in%20cond.jobs%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20self.jobs%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.new_fixed_size_interval_var(self.starts%5Bid_job%5D%2C%20job.time%2C%20name%3D%22%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(cond.jobs)%0A%20%20%20%20%20%20%20%20%20%20%20%20%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20%E3%82%B8%E3%83%A7%E3%83%96%E9%96%93%E4%BE%9D%E5%AD%98%E9%96%A2%E4%BF%82%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20idx%2C%20jdx%20in%20cond.prec%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.add(self.jobs%5Bidx%5D.end_expr()%20%3C%3D%20self.jobs%5Bjdx%5D.start_expr())%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20%E8%B3%87%E6%BA%90%E5%88%B6%E7%B4%84%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_res%2C%20res%20in%20enumerate(cond.ress)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20capacity%20%3D%20res.ub%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20intervals%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20demands%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(cond.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20job.res_usages%5Bid_res%5D%20%3D%3D%200%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%20intervals.append(self.jobs%5Bid_job%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20demands.append(job.res_usages%5Bid_res%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.add_cumulative(intervals%2C%20demands%2C%20capacity)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20%E7%9B%AE%E7%9A%84%E9%96%A2%E6%95%B0%3A%20makespan%0A%20%20%20%20%20%20%20%20%20%20%20%20self.objective%20%3D%20self.model.new_int_var(lb%3D0%2C%20ub%3Dhorizon%2C%20name%3D%22%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model.add_max_equality(self.objective%2C%20%5Binterval.end_expr()%20for%20interval%20in%20self.jobs%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model.minimize(self.objective)%0A%0A%20%20%20%20%20%20%20%20def%20solve(self%2C%20timeout%3A%20int%20%3D%20180)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver%20%3D%20cp_model.CpSolver()%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver.parameters.log_search_progress%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver.parameters.max_time_in_seconds%20%3D%20timeout%0A%20%20%20%20%20%20%20%20%20%20%20%20self.status%20%3D%20self.solver.solve(self.model)%0A%20%20%20%20return%20(Model2CpSat%2C)%0A%0A%0A%40app.cell%0Adef%20_(Model2CpSat%2C%20cond1)%3A%0A%20%20%20%20model4%20%3D%20Model2CpSat(cond1)%0A%20%20%20%20model4.solve()%0A%20%20%20%20return%20(model4%2C)%0A%0A%0A%40app.cell%0Adef%20_(model4)%3A%0A%20%20%20%20print%20(f%22Opt.value%20%3D%20%7Bmodel4.solver.value(model4.objective)%7D%22)%0A%0A%20%20%20%20for%20_id_job%2C%20interval%20in%20enumerate(model4.jobs)%3A%0A%20%20%20%20%20%20%20%20_val%20%3D%20model4.solver.value(interval.start_expr())%0A%20%20%20%20%20%20%20%20print(f%22s%5B%7B_id_job%7D%5D%20%3D%20%7B_val%7D%22)%0A%20%20%20%20return%20(interval%2C)%0A%0A%0A%40app.cell%0Adef%20_(Condition%2C%20Path%2C%20data_dir)%3A%0A%20%20%20%20_filepath%20%3D%20data_dir%20%2F%20Path(%22pat104.rcp%22)%0A%20%20%20%20cond2%20%3D%20Condition.from_file(_filepath)%0A%20%20%20%20return%20(cond2%2C)%0A%0A%0A%40app.cell%0Adef%20_(Model2Highs%2C%20cond2)%3A%0A%20%20%20%20model5%20%3D%20Model2Highs(cond2)%0A%20%20%20%20model5.solve()%0A%20%20%20%20return%20(model5%2C)%0A%0A%0A%40app.cell%0Adef%20_(Model2CpSat%2C%20cond2)%3A%0A%20%20%20%20model6%20%3D%20Model2CpSat(cond2)%0A%20%20%20%20model6.solve()%0A%20%20%20%20return%20(model6%2C)%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
fec0e5e0082d9a877c82de25bd07670b14f86075250c61bcf4524fb4ae9592e1