jobshop

import%20marimo%0A%0A__generated_with%20%3D%20%220.13.0%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%20pathlib%20import%20Path%0A%20%20%20%20from%20pprint%20import%20pprint%0A%20%20%20%20from%20typing%20import%20Self%0A%20%20%20%20import%20datetime%0A%20%20%20%20import%20random%0A%20%20%20%20import%20dotenv%0A%20%20%20%20import%20pandas%2C%20pyarrow%0A%20%20%20%20import%20pydantic%0A%20%20%20%20import%20plotly.express%0A%20%20%20%20import%20altair%0A%20%20%20%20from%20ortools.sat.python%20import%20cp_model%0A%20%20%20%20import%20highspy%0A%20%20%20%20import%20amplify_sched%0A%20%20%20%20import%20didppy%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20Path%2C%0A%20%20%20%20%20%20%20%20Self%2C%0A%20%20%20%20%20%20%20%20altair%2C%0A%20%20%20%20%20%20%20%20amplify_sched%2C%0A%20%20%20%20%20%20%20%20cp_model%2C%0A%20%20%20%20%20%20%20%20datetime%2C%0A%20%20%20%20%20%20%20%20didppy%2C%0A%20%20%20%20%20%20%20%20dotenv%2C%0A%20%20%20%20%20%20%20%20highspy%2C%0A%20%20%20%20%20%20%20%20os%2C%0A%20%20%20%20%20%20%20%20pandas%2C%0A%20%20%20%20%20%20%20%20plotly%2C%0A%20%20%20%20%20%20%20%20pprint%2C%0A%20%20%20%20%20%20%20%20pydantic%2C%0A%20%20%20%20%20%20%20%20random%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%20%E3%82%B8%E3%83%A7%E3%83%96%E3%82%B7%E3%83%A7%E3%83%83%E3%83%97%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%24J%20%7C%7C%20C_%7B%5Cmax%7D%24%20%E3%81%A8%E6%9B%B8%E3%81%8F.%20%0A%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%20%24J_1%2C%20%5Cdots%2C%20J_n%24%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%20%24J_j%24%20%E3%81%AB%E5%B1%9E%E3%81%99%E3%82%8B%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%20%24O_%7B1j%7D%2C%20%5Cdots%2C%20O_%7Bm_jj%7D%24.%20%E3%81%93%E3%81%AE%E9%A0%86%E3%81%A7%E5%87%A6%E7%90%86%E3%81%95%E3%82%8C%E3%82%8B.%20%0A%20%20%20%20%20%20%20%20-%20%E6%A9%9F%E6%A2%B0%20%24M_1%2C%20%5Cdots%2C%20M_m%24%0A%20%20%20%20%20%20%20%20-%20%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%20%24O_%7Bij%7D%24%20%E3%81%AF%E6%A9%9F%E6%A2%B0%20%24%5Cmu_%7Bij%7D%24%20%E3%81%A7%E4%BD%9C%E6%A5%AD%E6%99%82%E9%96%93%20%24p_%7Bij%7D%24%20%E3%81%8B%E3%81%91%E3%81%A6%E5%87%A6%E7%90%86%E3%81%99%E3%82%8B.%20%0A%20%20%20%20%20%20%20%20-%20%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AF%E4%B8%AD%E6%96%AD%E3%81%A7%E3%81%8D%E3%81%AA%E3%81%84%0A%20%20%20%20%20%20%20%20-%20%E6%9C%80%E5%BE%8C%E3%81%AE%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E7%B5%82%E4%BA%86%E6%99%82%E5%88%BB%E3%82%92%E6%9C%80%E5%B0%8F%E5%8C%96%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%20os.path.join(parent%2C%20%22data%22)%0A%20%20%20%20return%20data_dir%2C%20parent%0A%0A%0A%40app.cell%0Adef%20_(pydantic)%3A%0A%20%20%20%20class%20Task(pydantic.BaseModel)%3A%0A%20%20%20%20%20%20%20%20model_config%20%3D%20pydantic.ConfigDict(frozen%3DTrue)%0A%0A%20%20%20%20%20%20%20%20machine%3A%20int%20%3D%20pydantic.Field(...%2C%20ge%3D0%2C%20frozen%3DTrue)%0A%20%20%20%20%20%20%20%20time%3A%20int%20%3D%20pydantic.Field(...%2C%20ge%3D0%2C%20frozen%3DTrue)%0A%20%20%20%20return%20(Task%2C)%0A%0A%0A%40app.cell%0Adef%20_(Self%2C%20Task%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%0A%20%20%20%20%20%20%20%20tasks%3A%20list%5BTask%5D%20%3D%20pydantic.Field(frozen%3DTrue)%0A%0A%20%20%20%20%20%20%20%20def%20from_file(fname%3A%20str)%20-%3E%20list%5BSelf%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20with%20open(fname)%20as%20f%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20n%2C%20m%20%3D%20None%2C%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20machine%2C%20proc_time%20%3D%20%7B%7D%2C%20%7B%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20line%20in%20f%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20line%5B0%5D%20%3D%3D%20%22%23%22%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%20if%20n%20is%20None%20or%20m%20is%20None%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%20n%2C%20m%20%3D%20map(int%2C%20line.split())%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print(f%22%7Bn%3D%7D%2C%20%7Bm%3D%7D%22)%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%20L%20%3D%20list(map(int%2C%20line.split()))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20range(m)%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%20machine%5Bi%2C%20j%5D%20%3D%20L%5B2%20*%20j%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%20proc_time%5Bi%2C%20j%5D%20%3D%20L%5B2%20*%20j%20%2B%201%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20%2B%3D%201%0A%0A%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%20for%20i%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tasks%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20range(m)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tasks.append(Task(machine%3Dmachine%5Bi%2C%20j%5D%2C%20time%3Dproc_time%5Bi%2C%20j%5D))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20jobs.append(Job(tasks%3Dtasks))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20jobs%0A%20%20%20%20return%20(Job%2C)%0A%0A%0A%40app.cell%0Adef%20_(pandas%2C%20plotly)%3A%0A%20%20%20%20def%20plot_plotly(df%3A%20pandas.DataFrame)%3A%0A%20%20%20%20%20%20%20%20return%20plotly.express.timeline(%0A%20%20%20%20%20%20%20%20%20%20%20%20df%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20x_start%3D%22start%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20x_end%3D%22end%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%22resource%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22job%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20opacity%3D0.5%2C%0A%20%20%20%20%20%20%20%20).update_yaxes(categoryorder%3D%22category%20descending%22)%0A%20%20%20%20return%20(plot_plotly%2C)%0A%0A%0A%40app.cell%0Adef%20_(altair%2C%20pandas)%3A%0A%20%20%20%20def%20plot_altair(df%3A%20pandas.DataFrame)%3A%0A%20%20%20%20%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20altair.Chart(df)%0A%20%20%20%20%20%20%20%20%20%20%20%20.mark_bar()%0A%20%20%20%20%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%3D%22start%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x2%3D%22end%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20y%3D%22resource%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22job%22%2C%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%20.properties(width%3D%22container%22%2C%20height%3D400)%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20return%20(plot_altair%2C)%0A%0A%0A%40app.cell%0Adef%20_(Job%2C%20data_dir%2C%20os%2C%20pprint)%3A%0A%20%20%20%20fname1%20%3D%20os.path.join(data_dir%2C%20%22ft06.txt%22)%0A%20%20%20%20jobs1%20%3D%20Job.from_file(fname1)%0A%20%20%20%20pprint(jobs1)%0A%20%20%20%20return%20(jobs1%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%20OR-Tools%20%E3%81%AB%E3%82%88%E3%82%8B%E6%B1%82%E8%A7%A3%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Job%2C%20cp_model%2C%20datetime%2C%20pandas)%3A%0A%20%20%20%20class%20ModelCpSat%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20jobs%3A%20list%5BJob%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.jobs%20%3D%20jobs%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model%20%3D%20cp_model.CpModel()%0A%20%20%20%20%20%20%20%20%20%20%20%20num_machines%20%3D%20len(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20set(task.machine%20for%20job%20in%20self.jobs%20for%20task%20in%20job.tasks)%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%20self.machines%20%3D%20list(range(num_machines))%0A%20%20%20%20%20%20%20%20%20%20%20%20horizon%20%3D%20sum(task.time%20for%20job%20in%20self.jobs%20for%20task%20in%20job.tasks)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.starts%20%3D%20%5B%5BNone%20for%20task%20in%20job.tasks%5D%20for%20job%20in%20jobs%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20self.intervals%20%3D%20%5B%5BNone%20for%20task%20in%20job.tasks%5D%20for%20job%20in%20jobs%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20machine_to_interval%20%3D%20%7Bm%3A%20%5B%5D%20for%20m%20in%20self.machines%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20suffix%20%3D%20f%22_%7Bid_job%7D_%7Bid_task%7D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20start%20%3D%20self.model.new_int_var(0%2C%20horizon%2C%20%22start%22%20%2B%20suffix)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20interval%20%3D%20self.model.new_fixed_size_interval_var(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20start%2C%20task.time%2C%20%22interval%22%20%2B%20suffix%0A%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%20self.starts%5Bid_job%5D%5Bid_task%5D%20%3D%20start%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.intervals%5Bid_job%5D%5Bid_task%5D%20%3D%20interval%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20machine_to_interval%5Btask.machine%5D.append(interval)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20machine%20in%20machine_to_interval%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20len(machine_to_interval%5Bmachine%5D)%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.add_no_overlap(machine_to_interval%5Bmachine%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20id_task%20%3E%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%20curr%20%3D%20self.intervals%5Bid_job%5D%5Bid_task%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%20prev%20%3D%20self.intervals%5Bid_job%5D%5Bid_task%20-%201%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%20self.model.add(curr.start_expr()%20%3E%3D%20prev.end_expr())%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20makespan%20%3D%20self.model.new_int_var(0%2C%20horizon%2C%20%22makespan%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model.add_max_equality(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20makespan%2C%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%20self.intervals%5Bid_job%5D%5B-1%5D.end_expr()%0A%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(self.jobs)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5D%2C%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%20self.model.minimize(makespan)%0A%0A%20%20%20%20%20%20%20%20def%20solve(self%2C%20timeout%3A%20int%20%3D%2010)%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%0A%20%20%20%20%20%20%20%20def%20to_df(self)%20-%3E%20pandas.DataFrame%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20today%20%3D%20datetime.date.today()%0A%20%20%20%20%20%20%20%20%20%20%20%20l%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20start%20%3D%20self.solver.value(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.intervals%5Bid_job%5D%5Bid_task%5D.start_expr()%0A%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%20end%20%3D%20start%20%2B%20self.jobs%5Bid_job%5D.tasks%5Bid_task%5D.time%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20l.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dict(%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%20job%3Df%22job%7Bid_job%7D%22%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%20%20%20%20task%3Df%22task%7Bid_task%7D%22%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%20%20%20%20resource%3Df%22machine%7Bself.jobs%5Bid_job%5D.tasks%5Bid_task%5D.machine%7D%22%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%20%20%20%20start%3Dtoday%20%2B%20datetime.timedelta(start)%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%20%20%20%20end%3Dtoday%20%2B%20datetime.timedelta(end)%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)%0A%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%20df%20%3D%20pandas.DataFrame(l)%0A%20%20%20%20%20%20%20%20%20%20%20%20df%5B%22start%22%5D%20%3D%20pandas.to_datetime(df%5B%22start%22%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20df%5B%22end%22%5D%20%3D%20pandas.to_datetime(df%5B%22end%22%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20df%0A%20%20%20%20return%20(ModelCpSat%2C)%0A%0A%0A%40app.cell%0Adef%20_(ModelCpSat%2C%20jobs1)%3A%0A%20%20%20%20model1_cpsat%20%3D%20ModelCpSat(jobs1)%0A%20%20%20%20model1_cpsat.solve()%0A%20%20%20%20return%20(model1_cpsat%2C)%0A%0A%0A%40app.cell%0Adef%20_(model1_cpsat%2C%20plot_plotly)%3A%0A%20%20%20%20plot_plotly(model1_cpsat.to_df())%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20model1_cpsat%2C%20plot_altair)%3A%0A%20%20%20%20mo.ui.altair_chart(plot_altair(model1_cpsat.to_df()))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(model1_cpsat%2C%20plot_altair)%3A%0A%20%20%20%20plot_altair(model1_cpsat.to_df())%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%E6%95%B0%E7%90%86%E6%9C%80%E9%81%A9%E5%8C%96%E3%82%BD%E3%83%AB%E3%83%90%E3%83%BC%E3%81%AB%E3%82%88%E3%82%8B%E6%B1%82%E8%A7%A3%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%E5%90%84%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AB%E5%90%AB%E3%81%BE%E3%82%8C%E3%82%8B%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E6%95%B0%E3%81%AF%E6%A9%9F%E6%A2%B0%E3%81%AE%E6%95%B0%20%24m%24%20%E3%81%AB%E4%B8%80%E8%87%B4%E3%81%99%E3%82%8B%E3%81%A8%E4%BB%AE%E5%AE%9A%E3%81%99%E3%82%8B.%0A%0A%20%20%20%20%20%20%20%20%5Cbegin%7Balign*%7D%0A%20%20%20%20%20%20%20%20%26%5Cmin%20%26z%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%5Ctext%7Bs.t.%20%7D%20%26%20s_%7Bij%7D%20%2B%20p_%7Bij%7D%20-%20M%20(1%20-%20x_%7Bijkl%7D)%20%26%5Cleq%20s_%7Bkl%7D%20%5Cquad%20%26(%5Cforall%20j%20%5Cne%20k)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26%20x_%7Bijkl%7D%20%2B%20x_%7Bklij%7D%20%26%3D%201%20%5Cquad%20%26((i%2Cj)%20%5Cne%20(k%2Cl)%20%5Cland%20%5Ctext%7Bmachine%7D%20(i%2Cj)%20%3D%20%5Ctext%7Bmachine%7D%20(k%2Cl))%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26%20s_%7Bij%7D%20%2B%20p_%7Bij%7D%20%26%5Cle%20s_%7Bi%2Cj%2B1%7D%20%5Cquad%20%26(%5Cforall%20i%2C%20j%20%3D%201%2C%20%5Cdots%2C%20m-1)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26%20s_%7Bim%7D%20%26%5Cle%20z%20%5Cquad%20%26(%5Cforall%20i)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26%20s_%7Bi1%7D%20%26%5Cge%200%20%5Cquad%20%26(%5Cforall%20i)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26%20x_%7Bijkl%7D%20%26%5Cin%20%5C%7B%200%2C%201%20%5C%7D%20%5Cquad%20%26(%5Cforall%20(i%2Cj)%20%5Cne%20(k%2Cl))%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%0Adef%20_(Job%2C%20datetime%2C%20highspy%2C%20pandas)%3A%0A%20%20%20%20class%20_MyInterval%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20model%3A%20highspy.Highs%2C%20lb%3A%20int%2C%20ub%3A%20int%2C%20proctime%3A%20int)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lb%20%3D%20lb%0A%20%20%20%20%20%20%20%20%20%20%20%20self.ub%20%3D%20ub%0A%20%20%20%20%20%20%20%20%20%20%20%20self.start%20%3D%20model.addVariable(lb%3Dlb%2C%20ub%3Dub%20-%20proctime)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.time%20%3D%20proctime%0A%20%20%20%20%20%20%20%20%20%20%20%20self.end%20%3D%20self.start%20%2B%20self.time%0A%0A%0A%20%20%20%20def%20_my_add_no_overlap(model%3A%20highspy.Highs%2C%20tasks%3A%20list%5B_MyInterval%5D)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20for%20idx1%2C%20task1%20in%20enumerate(tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20idx2%2C%20task2%20in%20enumerate(tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20idx1%20%3E%3D%20idx2%3A%0A%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%20big_m%20%3D%20max(task1.ub%20-%20task2.lb%2C%20task2.ub%20-%20task1.lb)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tmp1%20%3D%20model.addBinary()%20%20%23%20%5B%20task1%20%5D%20%5B%20task2%20%5D%20%E3%81%AE%E9%A0%86%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tmp2%20%3D%20model.addBinary()%20%20%23%20%5B%20task2%20%5D%20%5B%20task1%20%5D%20%E3%81%AE%E9%A0%86%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20model.addConstrs(%0A%20%20%20%20%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%20%20%20%20%20task1.end%20-%20big_m%20*%20(1%20-%20tmp1)%20%3C%3D%20task2.start%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%20task2.end%20-%20big_m%20*%20(1%20-%20tmp2)%20%3C%3D%20task1.start%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%20tmp1%20%2B%20tmp2%20%3D%3D%201%2C%0A%20%20%20%20%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%20%20%20%20)%0A%0A%0A%20%20%20%20class%20ModelHighs%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20jobs%3A%20list%5BJob%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.jobs%20%3D%20jobs%0A%20%20%20%20%20%20%20%20%20%20%20%20num_machines%20%3D%20len(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20set(task.machine%20for%20job%20in%20self.jobs%20for%20task%20in%20job.tasks)%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%20self.machines%20%3D%20list(range(num_machines))%0A%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%20self.intervals%20%3D%20%5B%5BNone%20for%20task%20in%20job.tasks%5D%20for%20job%20in%20jobs%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20machine_to_interval%20%3D%20%7Bm%3A%20%5B%5D%20for%20m%20in%20self.machines%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20horizon%20%3D%20sum(task.time%20for%20job%20in%20self.jobs%20for%20task%20in%20job.tasks)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20interval%20%3D%20_MyInterval(self.model%2C%200%2C%20horizon%2C%20task.time)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.intervals%5Bid_job%5D%5Bid_task%5D%20%3D%20interval%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20machine_to_interval%5Btask.machine%5D.append(interval)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20machine%20in%20machine_to_interval%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20len(machine_to_interval%5Bmachine%5D)%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_my_add_no_overlap(self.model%2C%20machine_to_interval%5Bmachine%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20id_task%20%3E%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%20curr%20%3D%20self.intervals%5Bid_job%5D%5Bid_task%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%20prev%20%3D%20self.intervals%5Bid_job%5D%5Bid_task%20-%201%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%20self.model.addConstr(curr.start%20%3E%3D%20prev.end)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20makespan%20%3D%20self.model.addVariable(lb%3D0%2C%20ub%3Dhorizon)%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%20self.intervals%5Bid_job%5D%5B-1%5D.end%20%3C%3D%20makespan%0A%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(self.jobs)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5D%2C%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%20self.model.minimize(makespan)%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%20self.model.run()%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solution%20%3D%20self.model.getSolution()%0A%0A%20%20%20%20%20%20%20%20def%20to_df(self)%20-%3E%20pandas.DataFrame%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20today%20%3D%20datetime.date.today()%0A%20%20%20%20%20%20%20%20%20%20%20%20l%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20start%20%3D%20self.solution.col_value%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.intervals%5Bid_job%5D%5Bid_task%5D.start.index%0A%20%20%20%20%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%20%20%20%20%20%20%20%20start%20%3D%20round(start)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20end%20%3D%20start%20%2B%20self.jobs%5Bid_job%5D.tasks%5Bid_task%5D.time%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20l.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dict(%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%20job%3Df%22job%7Bid_job%7D%22%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%20%20%20%20task%3Df%22task%7Bid_task%7D%22%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%20%20%20%20resource%3Df%22machine%7Bself.jobs%5Bid_job%5D.tasks%5Bid_task%5D.machine%7D%22%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%20%20%20%20start%3Dtoday%20%2B%20datetime.timedelta(start)%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%20%20%20%20end%3Dtoday%20%2B%20datetime.timedelta(end)%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)%0A%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%20df%20%3D%20pandas.DataFrame(l)%0A%20%20%20%20%20%20%20%20%20%20%20%20df%5B%22start%22%5D%20%3D%20pandas.to_datetime(df%5B%22start%22%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20df%5B%22end%22%5D%20%3D%20pandas.to_datetime(df%5B%22end%22%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20df%0A%20%20%20%20return%20(ModelHighs%2C)%0A%0A%0A%40app.cell%0Adef%20_(ModelHighs%2C%20jobs1)%3A%0A%20%20%20%20model1_highs%20%3D%20ModelHighs(jobs1)%0A%20%20%20%20model1_highs.solve()%0A%20%20%20%20return%20(model1_highs%2C)%0A%0A%0A%40app.cell%0Adef%20_(model1_highs%2C%20plot_altair)%3A%0A%20%20%20%20plot_altair(model1_highs.to_df())%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%20FIXSTARS%20Amplify%20Scheduling%20Engine%20%E3%81%AB%E3%82%88%E3%82%8B%E6%B1%82%E8%A7%A3%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Job%2C%20amplify_sched%2C%20datetime%2C%20dotenv%2C%20os%2C%20pandas)%3A%0A%20%20%20%20dotenv.load_dotenv(dotenv.find_dotenv(usecwd%3DTrue))%0A%20%20%20%20token%20%3D%20os.environ%5B%22FIXSTARS_SE%22%5D%0A%0A%0A%20%20%20%20class%20ModelAmplifySe%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20jobs%3A%20list%5BJob%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.jobs%20%3D%20jobs%0A%20%20%20%20%20%20%20%20%20%20%20%20num_machines%20%3D%20len(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20set(task.machine%20for%20job%20in%20self.jobs%20for%20task%20in%20job.tasks)%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%20self.machines%20%3D%20list(range(num_machines))%0A%20%20%20%20%20%20%20%20%20%20%20%20self.se_machines%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20amplify_sched.Machine(name%3Df%22machine%7Bmidx%7D%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20midx%20in%20self.machines%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%20self.model%20%3D%20amplify_sched.Model()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20semachine%20in%20self.se_machines%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.machines.add(machine%3Dsemachine)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.se_jobs%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20amplify_sched.Job(name%3Df%22job%7Bjidx%7D%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20jidx%2C%20_%20in%20enumerate(self.jobs)%0A%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%20for%20idx%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sejob%20%3D%20self.se_jobs%5Bidx%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.jobs.add(sejob)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20jdx%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20semachine%20%3D%20self.se_machines%5Btask.machine%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20setask%20%3D%20amplify_sched.Task()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20setask.processing_times%5Bsemachine%5D%20%3D%20task.time%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.jobs%5Bsejob.name%5D.append(setask)%0A%0A%20%20%20%20%20%20%20%20def%20solve(self%2C%20timeout%3A%20int%20%3D%205)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solution%20%3D%20self.model.solve(token%3Dtoken%2C%20timeout%3Dtimeout)%0A%0A%20%20%20%20%20%20%20%20def%20get_makespan(self)%20-%3E%20int%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20int(self.solution.table%5B%22Finish%22%5D.max())%0A%0A%20%20%20%20%20%20%20%20def%20to_df(self)%20-%3E%20pandas.DataFrame%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20sol_df%20%3D%20self.solution.table%0A%20%20%20%20%20%20%20%20%20%20%20%20today%20%3D%20datetime.date.today()%0A%20%20%20%20%20%20%20%20%20%20%20%20l%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sejob%20%3D%20self.se_jobs%5Bid_job%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20start%20%3D%20int(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sol_df%5Bsol_df%5B%22Job%22%5D%20%3D%3D%20sejob.name%5D%5B%22Start%22%5D.reset_index(%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%20drop%3DTrue%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)%5Bid_task%5D%0A%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%20end%20%3D%20start%20%2B%20self.jobs%5Bid_job%5D.tasks%5Bid_task%5D.time%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20l.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dict(%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%20job%3Df%22job%7Bid_job%7D%22%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%20%20%20%20task%3Df%22task%7Bid_task%7D%22%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%20%20%20%20resource%3Df%22machine%7Bself.jobs%5Bid_job%5D.tasks%5Bid_task%5D.machine%7D%22%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%20%20%20%20start%3Dtoday%20%2B%20datetime.timedelta(start)%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%20%20%20%20end%3Dtoday%20%2B%20datetime.timedelta(end)%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)%0A%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%20df%20%3D%20pandas.DataFrame(l)%0A%20%20%20%20%20%20%20%20%20%20%20%20df%5B%22start%22%5D%20%3D%20pandas.to_datetime(df%5B%22start%22%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20df%5B%22end%22%5D%20%3D%20pandas.to_datetime(df%5B%22end%22%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20df%0A%20%20%20%20return%20(ModelAmplifySe%2C)%0A%0A%0A%40app.cell%0Adef%20_(ModelAmplifySe%2C%20jobs1)%3A%0A%20%20%20%20model1_amplify%20%3D%20ModelAmplifySe(jobs1)%0A%20%20%20%20model1_amplify.solve()%0A%0A%20%20%20%20print(f%22makespan%20%3D%20%7Bmodel1_amplify.get_makespan()%7D%22)%0A%20%20%20%20return%20(model1_amplify%2C)%0A%0A%0A%40app.cell%0Adef%20_(model1_amplify)%3A%0A%20%20%20%20model1_amplify.solution.timeline(machine_view%3DTrue)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(model1_amplify%2C%20plot_altair)%3A%0A%20%20%20%20plot_altair(model1_amplify.to_df())%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%88%E3%82%8A%E5%A4%A7%E3%81%8D%E3%81%84%E5%95%8F%E9%A1%8C%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Job%2C%20Task%2C%20random)%3A%0A%20%20%20%20def%20gen_data(n_jobs%3A%20int%2C%20n_machines%3A%20int)%20-%3E%20list%5BJob%5D%3A%0A%20%20%20%20%20%20%20%20random.seed(0)%0A%20%20%20%20%20%20%20%20jobs%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20id_job%20in%20range(n_jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20machines%20%3D%20list(range(n_machines))%0A%20%20%20%20%20%20%20%20%20%20%20%20random.shuffle(machines)%0A%20%20%20%20%20%20%20%20%20%20%20%20tasks%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%20in%20range(n_machines)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20machine%20%3D%20machines%5Bid_task%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20time%20%3D%20random.randint(1%2C%2010)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tasks.append(Task(machine%3Dmachine%2C%20time%3Dtime))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20jobs.append(Job(tasks%3Dtasks))%0A%0A%20%20%20%20%20%20%20%20return%20jobs%0A%20%20%20%20return%20(gen_data%2C)%0A%0A%0A%40app.cell%0Adef%20_(gen_data%2C%20pprint)%3A%0A%20%20%20%20jobs2%20%3D%20gen_data(45%2C%2015)%0A%20%20%20%20pprint(jobs2)%0A%20%20%20%20return%20(jobs2%2C)%0A%0A%0A%40app.cell%0Adef%20_(ModelCpSat%2C%20jobs2)%3A%0A%20%20%20%20model2_cpsat%20%3D%20ModelCpSat(jobs2)%0A%20%20%20%20model2_cpsat.solve()%0A%20%20%20%20return%20(model2_cpsat%2C)%0A%0A%0A%40app.cell%0Adef%20_(model2_cpsat%2C%20plot_plotly)%3A%0A%20%20%20%20plot_plotly(model2_cpsat.to_df())%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20%23%20model2_highs%20%3D%20ModelHighs(jobs2)%0A%20%20%20%20%23%20model2_highs.solve()%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20%23%20plot_altair(model2_highs.to_df())%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ModelAmplifySe%2C%20jobs2)%3A%0A%20%20%20%20model2_amplify%20%3D%20ModelAmplifySe(jobs2)%0A%20%20%20%20model2_amplify.solve(timeout%3D5)%0A%0A%20%20%20%20print(f%22makespan%20%3D%20%7Bmodel2_amplify.get_makespan()%7D%22)%0A%20%20%20%20return%20(model2_amplify%2C)%0A%0A%0A%40app.cell%0Adef%20_(model2_amplify%2C%20plot_plotly)%3A%0A%20%20%20%20plot_plotly(model2_amplify.to_df())%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%BB%96%E3%81%AE%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%20ta50%20%E3%81%AF%E6%9C%80%E9%81%A9%E8%A7%A3%E3%81%AF%E7%9F%A5%E3%82%89%E3%82%8C%E3%81%A6%E3%81%84%E3%81%AA%E3%81%84.%20%0A%0A%20%20%20%20%20%20%20%20bounds%0A%0A%20%20%20%20%20%20%20%20-%20upper%3A%201923%0A%20%20%20%20%20%20%20%20-%20lower%3A%201833%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_(os%2C%20parent)%3A%0A%20%20%20%20instance_dir%20%3D%20os.path.join(parent%2C%20%22jsplib%2Finstances%22)%0A%20%20%20%20return%20(instance_dir%2C)%0A%0A%0A%40app.cell%0Adef%20_(Job%2C%20instance_dir%2C%20os)%3A%0A%20%20%20%20fname3%20%3D%20os.path.join(instance_dir%2C%20%22ta50%22)%0A%20%20%20%20jobs3%20%3D%20Job.from_file(fname3)%0A%20%20%20%20return%20(jobs3%2C)%0A%0A%0A%40app.cell%0Adef%20_(ModelAmplifySe%2C%20jobs3%2C%20mo)%3A%0A%20%20%20%20model3_amplify%20%3D%20ModelAmplifySe(jobs3)%0A%20%20%20%20model3_amplify.solve(timeout%3D10)%0A%0A%20%20%20%20mo.md(f%22makespan%20%3D%20%7Bmodel3_amplify.get_makespan()%7D%22)%0A%20%20%20%20return%20(model3_amplify%2C)%0A%0A%0A%40app.cell%0Adef%20_(model3_amplify%2C%20plot_plotly)%3A%0A%20%20%20%20plot_plotly(model3_amplify.to_df())%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ModelCpSat%2C%20jobs3%2C%20mo)%3A%0A%20%20%20%20model3_cpsat%20%3D%20ModelCpSat(jobs3)%0A%20%20%20%20model3_cpsat.solve(timeout%3D10)%0A%0A%20%20%20%20mo.md(f%22makespan%20%3D%20%7Bround(model3_cpsat.solver.objective_value)%7D%22)%0A%20%20%20%20return%20(model3_cpsat%2C)%0A%0A%0A%40app.cell%0Adef%20_(model3_cpsat%2C%20plot_plotly)%3A%0A%20%20%20%20plot_plotly(model3_cpsat.to_df())%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%20didp%20%E3%81%A7%E3%81%AE%E6%B1%82%E8%A7%A3%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%E7%8A%B6%E6%85%8B%0A%0A%20%20%20%20%20%20%20%20-%20%24%5Ctext%7BQ%7D%24%3A%20set%20%E5%A4%89%E6%95%B0.%20%E9%85%8D%E7%BD%AE%E3%81%95%E3%82%8C%E3%81%A6%E3%81%84%E3%81%AA%E3%81%84%E3%82%BF%E3%82%B9%E3%82%AF%E3%81%AE%E9%9B%86%E5%90%88%E3%82%92%E8%A1%A8%E3%81%99.%20%0A%20%20%20%20%20%20%20%20-%20%24%5Ctext%7Btm%7D_m%20%5Cspace%20(%5Cforall%20m%3A%20%5Ctext%7Bmachine%7D)%24%3A%20%E6%A9%9F%E6%A2%B0%E3%81%94%E3%81%A8%E3%81%AB%20makespan%20%E3%82%92%E4%BF%9D%E6%8C%81%E3%81%99%E3%82%8B.%20%0A%20%20%20%20%20%20%20%20-%20%24%5Ctext%7Btj%7D_j%20%5Cspace%20(%5Cforall%20j%3A%20%5Ctext%7Bjob%7D)%24%3A%20%E3%82%B8%E3%83%A7%E3%83%96%E3%81%94%E3%81%A8%E3%81%AB%20makespan%20%E3%82%92%E4%BF%9D%E6%8C%81%E3%81%99%E3%82%8B.%20%0A%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-%20%24%5Ctext%7Bmakespan%7D%20%3A%3D%20%5Cmax%20%5C%7B%20%5Ctext%7Btm%7D_m%2C%20%5Ctext%7Btj%7D_j%20%5Cmid%20m%3A%20%5Ctext%7Bmachine%7D%2C%20%5Cspace%20j%3A%20%5Ctext%7Bjob%7D%20%5C%7D%24%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20%E6%9B%B4%E6%96%B0%E8%A6%8F%E5%89%87%0A%0A%20%20%20%20%20%20%20%20-%20%E3%82%BF%E3%82%B9%E3%82%AF%20%24%5Ctext%7Btask%7D%20%5Cin%20Q%24%20%E3%81%AF%E5%85%A8%E3%81%A6%E3%81%AE%E5%85%88%E8%A1%8C%E3%82%BF%E3%82%B9%E3%82%AF%E3%81%8C%20%24Q%24%20%E3%81%AB%E5%B1%9E%E3%81%97%E3%81%A6%E3%81%84%E3%81%AA%E3%81%84%E6%99%82%E9%85%8D%E7%BD%AE%E5%8F%AF%E8%83%BD.%20%0A%20%20%20%20%20%20%20%20-%20%24%5Ctext%7Btask%7D%24%20%E3%81%8C%E9%85%8D%E7%BD%AE%E3%81%95%E3%82%8C%E3%81%9F%E5%A0%B4%E5%90%88%2C%20%E3%81%9D%E3%82%8C%E3%82%92%20%24Q%24%20%E3%81%8B%E3%82%89%E5%8F%96%E3%82%8A%E9%99%A4%E3%81%8F.%20%0A%20%20%20%20%20%20%20%20-%20%24%5Ctext%7Btask%7D%24%20%E3%81%8C%E9%85%8D%E7%BD%AE%E3%81%95%E3%82%8C%E3%81%9F%E5%A0%B4%E5%90%88%2C%20%E3%82%BF%E3%82%B9%E3%82%AF%E3%82%92%E5%87%A6%E7%90%86%E3%81%99%E3%82%8B%E6%A9%9F%E6%A2%B0%20%24m%24%20%E3%81%A8%E3%82%BF%E3%82%B9%E3%82%AF%E3%81%AE%E5%B1%9E%E3%81%99%E3%82%8B%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%AB%E5%AF%BE%E3%81%97%E3%81%A6%E4%BB%A5%E4%B8%8B%E3%81%AE%E3%82%88%E3%81%86%E3%81%AB%E6%9B%B4%E6%96%B0%E3%81%99%E3%82%8B.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24%5Ctext%7Btm%7D_m%20%5Cleftarrow%20%5Cmax(%5Ctext%7Btm%7D_m%20%2B%20t_%5Ctext%7Btask%7D%2C%20%5Cspace%20%5Ctext%7Btj%7D_j%20%2B%20t_%5Ctext%7Btask%7D)%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24%5Ctext%7Btj%7D_j%20%5Cleftarrow%20%5Cmax(%5Ctext%7Btm%7D_m%20%2B%20t_%5Ctext%7Btask%7D%2C%20%5Cspace%20%5Ctext%7Btj%7D_j%20%2B%20t_%5Ctext%7Btask%7D)%24%0A%20%20%20%20%20%20%20%20-%20%E4%B8%8A%E8%A8%98%E6%9B%B4%E6%96%B0%E3%81%AE%E5%BE%8C%2C%20%E7%9B%AE%E7%9A%84%E9%96%A2%E6%95%B0%E3%82%92%E5%86%8D%E8%A8%88%E7%AE%97%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%0Adef%20_(Job%2C%20didppy)%3A%0A%20%20%20%20class%20ModelDidp%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20jobs%3A%20list%5BJob%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.jobs%20%3D%20jobs%0A%20%20%20%20%20%20%20%20%20%20%20%20n_tasks%20%3D%20sum(len(job.tasks)%20for%20job%20in%20self.jobs)%0A%20%20%20%20%20%20%20%20%20%20%20%20n_machines%20%3D%20len(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20set(task.machine%20for%20job%20in%20self.jobs%20for%20task%20in%20job.tasks)%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%20self.model%20%3D%20didppy.Model()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20objtype_task%20%3D%20self.model.add_object_type(number%3Dn_tasks)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20remaining%20%3D%20self.model.add_set_var(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20object_type%3Dobjtype_task%2C%20target%3Dlist(range(n_tasks))%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%20cur_time_per_machine%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20self.model.add_int_var(target%3D0)%20for%20_%20in%20range(n_machines)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.add_int_resource_var(target%3D0%2C%20less_is_better%3DTrue)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_%20in%20range(n_machines)%0A%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%20cur_time_per_job%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20self.model.add_int_var(target%3D0)%20for%20_%20in%20self.jobs%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model.add_int_resource_var(target%3D0%2C%20less_is_better%3DTrue)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_%20in%20self.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%20self.model.add_base_case(%5Bremaining.is_empty()%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20task_to_time%20%3D%20self.model.add_int_table(%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20%20%20%20%20%5Btask.time%20for%20job%20in%20self.jobs%20for%20task%20in%20job.tasks%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20task_to_machine%20%3D%20self.model.add_int_table(%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20%20%20%20%20%5Btask.machine%20for%20job%20in%20self.jobs%20for%20task%20in%20job.tasks%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20precs%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20id_jobtask%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%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%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20precs.append(prec.copy())%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prec.add(id_jobtask)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20id_jobtask%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20task_to_prec%20%3D%20self.model.add_set_table(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20precs%2C%20object_type%3Dobjtype_task%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%20id_jobtask%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20id_job%2C%20job%20in%20enumerate(self.jobs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20id_task%2C%20task%20in%20enumerate(job.tasks)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sched%20%3D%20didppy.Transition(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20name%3Df%22sched_job%7Bid_job%7D_task%7Bid_task%7D%22%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%20cost%3D(%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%20didppy.max(%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%20didppy.IntExpr.state_cost()%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%20%20%20%20%20%20%20%20didppy.max(%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%20%20%20%20%20cur_time_per_machine%5Btask.machine%5D%20%2B%20task.time%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%20%20%20%20%20%20%20%20%20%20%20%20cur_time_per_job%5Bid_job%5D%20%2B%20task.time%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%20%20%20%20%20%20%20%20)%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%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)%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%20effects%3D%5B%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(remaining%2C%20remaining.remove(id_jobtask))%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%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%20%20%20%20%20%20%20%20cur_time_per_job%5Bid_job%5D%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%20%20%20%20%20%20%20%20didppy.max(%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%20%20%20%20%20cur_time_per_machine%5Btask.machine%5D%20%2B%20task.time%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%20%20%20%20%20%20%20%20%20%20%20%20cur_time_per_job%5Bid_job%5D%20%2B%20task.time%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%20%20%20%20%20%20%20%20)%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%20%20%20%20)%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%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%20%20%20%20%20%20%20%20cur_time_per_machine%5Btask.machine%5D%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%20%20%20%20%20%20%20%20didppy.max(%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%20%20%20%20%20cur_time_per_machine%5Btask.machine%5D%20%2B%20task.time%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%20%20%20%20%20%20%20%20%20%20%20%20cur_time_per_job%5Bid_job%5D%20%2B%20task.time%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%20%20%20%20%20%20%20%20)%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%20%20%20%20)%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%5D%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%20preconditions%3D%5B%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%20remaining.contains(id_jobtask)%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%20%20%20%20remaining.isdisjoint(task_to_prec%5Bid_jobtask%5D)%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%5D%2C%0A%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%20self.model.add_transition(sched)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20id_jobtask%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model.add_dual_bound(0)%0A%0A%20%20%20%20%20%20%20%20def%20solve(self%2C%20timeout%3D10%2C%20threads%3A%20int%20%3D%208)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver%20%3D%20didppy.CABS(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.model%2C%20threads%3Dthreads%2C%20quiet%3DFalse%2C%20time_limit%3Dtimeout%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%20%23%20self.solver%20%3D%20didppy.LNBS(%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20%20%20%20%20self.model%2C%20threads%3Dthreads%2C%20quiet%3DFalse%2C%20time_limit%3Dtimeout%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solution%3A%20didppy.Solution%20%3D%20self.solver.search()%0A%20%20%20%20return%20(ModelDidp%2C)%0A%0A%0A%40app.cell%0Adef%20_(ModelDidp%2C%20jobs1%2C%20mo)%3A%0A%20%20%20%20model1_didp%20%3D%20ModelDidp(jobs1)%0A%20%20%20%20model1_didp.solve(threads%3D10%2C%20timeout%3D10)%0A%0A%20%20%20%20mo.md(f%22makespan%20%3D%20%7Bround(model1_didp.solution.cost)%7D%22)%0A%20%20%20%20return%20(model1_didp%2C)%0A%0A%0A%40app.cell%0Adef%20_(model1_didp)%3A%0A%20%20%20%20model1_didp.solution.is_optimal%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(model1_didp)%3A%0A%20%20%20%20for%20_t%20in%20model1_didp.solution.transitions%3A%0A%20%20%20%20%20%20%20%20print(_t.name)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ModelDidp%2C%20jobs2%2C%20mo)%3A%0A%20%20%20%20model2_didp%20%3D%20ModelDidp(jobs2)%0A%20%20%20%20model2_didp.solve(threads%3D10%2C%20timeout%3D10)%0A%0A%20%20%20%20mo.md(f%22makespan%20%3D%20%7Bround(model2_didp.solution.cost)%7D%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ModelDidp%2C%20jobs3%2C%20mo)%3A%0A%20%20%20%20model3_didp%20%3D%20ModelDidp(jobs3)%0A%20%20%20%20model3_didp.solve(threads%3D10%2C%20timeout%3D10)%0A%0A%20%20%20%20mo.md(f%22makespan%20%3D%20%7Bround(model3_didp.solution.cost)%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%E9%9B%A2%E6%8E%A5%E5%AE%9A%E5%BC%8F%E5%8C%96%E3%81%AE%E3%82%B0%E3%83%A9%E3%83%95%E3%81%AB%E3%82%88%E3%82%8B%E8%A1%A8%E7%A4%BA%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%20JSP%20%E3%81%AF%20%E3%82%BF%E3%82%B9%E3%82%AF%E3%82%92%E3%83%8E%E3%83%BC%E3%83%89%2C%20%E4%BE%9D%E5%AD%98%E9%96%A2%E4%BF%82%E3%82%84%E5%90%8C%E6%99%82%E5%87%A6%E7%90%86%E7%A6%81%E6%AD%A2%E8%A6%8F%E5%89%87%E3%82%92%E3%82%A8%E3%83%83%E3%82%B8%E3%81%A7%E8%A1%A8%E7%8F%BE%E3%81%97%E3%81%9F%E3%82%B0%E3%83%A9%E3%83%95%E3%81%8B%E3%82%89%E3%82%A8%E3%83%83%E3%82%B8%E3%82%92%E9%81%B8%E6%8A%9E%E3%81%99%E3%82%8B%E5%95%8F%E9%A1%8C%E3%81%A8%E3%81%97%E3%81%A6%E8%A1%A8%E7%8F%BE%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%81%8C%E3%81%A7%E3%81%8D%E3%82%8B.%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20%E5%8F%82%E8%80%83%0A%0A%20%20%20%20%20%20%20%20-%20https%3A%2F%2Facrogenesis.com%2For-tools%2Fdocumentation%2Fuser_manual%2Fmanual%2Fls%2Fjobshop_def_data.html%0A%20%20%20%20%20%20%20%20-%20https%3A%2F%2Fzenn.dev%2Ffusic%2Farticles%2F0fed6d5dfbdeb5%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%AE%9A%E6%95%B0%0A%0A%20%20%20%20%20%20%20%20-%20%24J%24%3A%20%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E9%9B%86%E5%90%88%0A%20%20%20%20%20%20%20%20-%20%24M%24%3A%20%E3%83%9E%E3%82%B7%E3%83%B3%E3%81%AE%E9%9B%86%E5%90%88%0A%20%20%20%20%20%20%20%20-%20%24O%24%3A%20%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E9%9B%86%E5%90%88%0A%20%20%20%20%20%20%20%20-%20%24O_j%24%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%AE%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E9%9B%86%E5%90%88%0A%20%20%20%20%20%20%20%20-%20%24O_m%24%3A%20%E3%83%9E%E3%82%B7%E3%83%B3%20%24m%24%20%E3%81%A7%E5%87%A6%E7%90%86%E3%81%99%E3%82%8B%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E9%9B%86%E5%90%88%0A%20%20%20%20%20%20%20%20-%20%24t_o%24%3A%20%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%20%24o%24%20%E3%81%AE%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20%E3%82%B0%E3%83%A9%E3%83%95%0A%0A%20%20%20%20%20%20%20%20-%20%E3%83%8E%E3%83%BC%E3%83%89%20%24N%20%3A%3D%20O%20%5Ccup%20%5C%7B%20%5Ctext%7Bsource%7D%2C%20%5Ctext%7Btarget%7D%20%5C%7D%24%0A%20%20%20%20%20%20%20%20-%20%E3%82%A8%E3%83%83%E3%82%B8%20%24E%20%3A%3D%20E%5Ec%20%5Ccup%20E%5Ed%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Conjunctive%20Edges%20%24E%5Ec%24%3A%20%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%20%24o%24%20%E3%81%A8%20%24o'%24%20%E3%81%8C%E5%90%8C%E3%81%98%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AB%E5%B1%9E%E3%81%97%E3%81%A6%E3%81%8A%E3%82%8A%2C%20%24o%24%20%E3%81%AE%E5%BE%8C%E3%81%AB%20%24o'%24%20%E3%82%92%E5%87%A6%E7%90%86%E3%81%97%E3%81%AA%E3%81%91%E3%82%8C%E3%81%B0%E3%81%AA%E3%82%89%E3%81%AA%E3%81%84%E5%A0%B4%E5%90%88%2C%20%24(o%2C%20o')%20%5Cin%20E%5Ec%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E3%81%BE%E3%81%9F%2C%20%24o%24%20%E3%81%8C%E3%81%82%E3%82%8B%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E6%9C%80%E5%88%9D%E3%81%AE%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%A7%E3%81%82%E3%82%8B%E3%81%A8%E3%81%8D%20%24(%5Ctext%7Bsource%7D%2C%20o)%20%5Cin%20E%5Ec%24.%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%24o%24%20%E3%81%8C%E3%81%82%E3%82%8B%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E6%9C%80%E5%BE%8C%E3%81%AE%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%A7%E3%81%82%E3%82%8B%E3%81%A8%E3%81%8D%20%24(o%2C%20%5Ctext%7Btarget%7D)%20%5Cin%20E%5Ec%24.%20%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Disjunctive%20Edges%20%24E%5Ed%24%3A%20%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%20%24o%24%20%E3%81%A8%20%24o'%24%20%E3%81%8C%E5%90%8C%E3%81%98%E3%83%9E%E3%82%B7%E3%83%B3%E3%81%A7%E5%87%A6%E7%90%86%E3%81%95%E3%82%8C%E3%82%8B%E3%81%A8%E3%81%8D%2C%20%24(o%2C%20o')%20%5Cin%20E%5Ed%24%20%E3%81%8B%E3%81%A4%20%24(o'%2C%20o)%20%5Cin%20E%5Ed%24.%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E3%81%93%E3%81%AE%E3%82%A8%E3%83%83%E3%82%B8%E3%81%AF%E5%8F%8C%E6%96%B9%E5%90%91%E3%81%AE%E3%81%86%E3%81%A1%E3%81%A9%E3%81%A1%E3%82%89%E3%81%8B%E3%82%92%E9%81%B8%E6%8A%9E%E3%81%97%2C%20%E9%81%B8%E6%8A%9E%E3%81%95%E3%82%8C%E3%81%9F%E3%82%A8%E3%83%83%E3%82%B8%E3%81%AB%E3%82%88%E3%82%8A%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E5%87%A6%E7%90%86%E9%A0%86%E5%BA%8F%E3%81%8C%E5%AE%9A%E3%81%BE%E3%82%8B.%20%0A%0A%20%20%20%20%20%20%20%20%E3%81%93%E3%81%AE%E3%82%B0%E3%83%A9%E3%83%95%E3%81%AE%E3%82%A8%E3%83%83%E3%82%B8%E3%81%A7%E7%B9%8B%E3%81%8C%E3%82%8C%E3%81%9F%E3%83%8E%E3%83%BC%E3%83%89(%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3)%E3%81%AE%E9%96%93%E3%81%AB%E3%81%AF%E5%87%A6%E7%90%86%E9%A0%86%E5%BA%8F%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%20Conjunctive%20edge%20%E3%81%AF%E5%90%8C%E4%B8%80%E3%82%B8%E3%83%A7%E3%83%96%E5%86%85%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E9%A0%86%E5%BA%8F%E9%96%A2%E4%BF%82%E3%82%92%E8%A1%A8%E3%81%97%2C%20%0A%20%20%20%20%20%20%20%20Disjunctive%20edge%20%E3%81%AF%E5%90%8C%E4%B8%80%E3%83%9E%E3%82%B7%E3%83%B3%E3%81%A7%E5%87%A6%E7%90%86%E3%81%99%E3%82%8B%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E9%96%93%E3%81%AE%E9%A0%86%E5%BA%8F%E9%96%A2%E4%BF%82%E3%82%92%E8%A1%A8%E3%81%99.%20%0A%0A%20%20%20%20%20%20%20%20%23%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_e%20%5Cin%20%5C%7B%200%2C%201%20%5C%7D%20%5Cspace%20(e%20%5Cin%20E)%24%3A%20%E3%82%A8%E3%83%83%E3%82%B8%20%24e%24%20%E3%82%92%E9%81%B8%E6%8A%9E%E3%81%99%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AE%E3%81%BF%20%241%24.%0A%20%20%20%20%20%20%20%20-%20%24s_n%20%5Cin%20%5Cmathbb%7BZ%7D%20%5Cspace%20(n%20%5Cin%20N)%24%3A%20%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E9%96%8B%E5%A7%8B%E6%99%82%E5%88%BB.%20%24%5Ctext%7Bsource%7D%24%20%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E9%96%8B%E5%A7%8B%E6%99%82%E5%88%BB%E3%81%AF%200%2C%20%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%82%82%200%20%E3%81%A8%E3%81%99%E3%82%8B.%20%0A%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%24e%20%3D%20(u%2C%20v)%24%20%E3%81%A8%E3%81%99%E3%82%8B.%20%E3%81%93%E3%81%AE%E3%81%A8%E3%81%8D%20%24x_e%20%3D%201%20%5CRightarrow%20s_u%20%2B%20t_u%20%5Cleq%20s_v%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24e%20%5Cin%20E%5Ec%20%5CRightarrow%20x_e%20%3D%201%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24(u%2C%20v)%20%5Cin%20E%5Ed%20%5CRightarrow%20x_%7B(u%2Cv)%7D%20%2B%20x_%7B(v%2Cu)%7D%20%3D%201%24%0A%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-%20%24s_%5Ctext%7Btarget%7D%24%20%E3%81%8C%20makespan%20%E3%82%92%E8%A1%A8%E3%81%99.%20%E3%81%93%E3%82%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(r%22%22%22%23%23%20%E5%B7%A1%E5%9B%9E%E8%B7%AF%E5%88%B6%E7%B4%84%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%AE%9F%E8%A3%85%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%E4%B8%8A%E8%A8%98%E3%81%AE%E3%82%B0%E3%83%A9%E3%83%95%E3%81%AB%E3%83%9E%E3%82%B7%E3%83%B3%E8%87%AA%E4%BD%93%E3%82%92%E3%83%8E%E3%83%BC%E3%83%89%E3%81%A8%E3%81%97%E3%81%A6%E8%B6%B3%E3%81%97%2C%20%0A%20%20%20%20%20%20%20%20disjunctive%20edge%20%E3%81%AE%E3%81%BF%E3%82%92%E8%BE%BF%E3%81%A3%E3%81%A6%E3%83%9E%E3%82%B7%E3%83%B3%E3%81%94%E3%81%A8%E3%81%AB%E9%A0%86%E5%9B%9E%E8%B7%AF%E3%82%92%E4%BD%9C%E6%88%90%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%81%A7%E3%83%9E%E3%82%B7%E3%83%B3%E5%86%85%E3%81%A7%E3%81%AE%E5%AE%9F%E8%A1%8C%E9%A0%86%E3%82%92%E8%A8%98%E8%BF%B0%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%81%8C%E3%81%A7%E3%81%8D%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%0Adef%20_(Job%2C%20cp_model)%3A%0A%20%20%20%20class%20ModelCpSatArc%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20jobs%3A%20list%5BJob%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20machines%20%3D%20sorted(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20list(set(task.machine%20for%20job%20in%20jobs%20for%20task%20in%20job.tasks))%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%BF%E3%82%B9%E3%82%AF%E3%81%AB%200%20%E3%81%8B%E3%82%89%E7%95%AA%E5%8F%B7%E3%82%92%E5%89%B2%E3%82%8A%E6%8C%AF%E3%82%8B.%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20source%20%E3%81%A8%20target%20%E3%81%AF%E3%81%9D%E3%82%8C%E3%81%9E%E3%82%8C%20-1%2C%20-2%20%E3%81%A8%E3%81%99%E3%82%8B.%0A%20%20%20%20%20%20%20%20%20%20%20%20task_indices%20%3D%20%5B%5D%0A%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%20for%20job%20in%20jobs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20indices%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20task%20in%20job.tasks%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20indices.append(idx)%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%20task_indices.append(indices)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20all_tasks%20%3D%20%5Btask%20for%20job%20in%20jobs%20for%20task%20in%20job.tasks%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20horizon%20%3D%20sum(task.time%20for%20job%20in%20jobs%20for%20task%20in%20job.tasks)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20model%20%3D%20cp_model.CpModel()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20edges%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20starts%20%3D%20%7B%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20start%20time%0A%20%20%20%20%20%20%20%20%20%20%20%20starts%5B-1%5D%20%3D%20model.new_constant(0)%0A%20%20%20%20%20%20%20%20%20%20%20%20starts%5B-2%5D%20%3D%20model.new_int_var(0%2C%20horizon%2C%20%22%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20indices%20in%20task_indices%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20idx%20in%20indices%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20starts%5Bidx%5D%20%3D%20model.new_int_var(0%2C%20horizon%2C%20%22%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Conjunctive%20Edges%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20indices%20in%20task_indices%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edges%5B(-1%2C%20indices%5B0%5D)%5D%20%3D%20model.new_constant(1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edges%5B(indices%5B-1%5D%2C%20-2)%5D%20%3D%20model.new_constant(1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20i%2C%20_%20in%20enumerate(indices)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20i%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%20edges%5B(indices%5Bi%20-%201%5D%2C%20indices%5Bi%5D)%5D%20%3D%20model.new_constant(1)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Disjunctive%20Edges%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20m%20in%20machines%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20indices_m%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idx%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20indices%2C%20job%20in%20zip(task_indices%2C%20jobs)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20idx%2C%20task%20in%20zip(indices%2C%20job.tasks)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20task.machine%20%3D%3D%20m%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5D%20%2B%20%5B-3%20-%20m%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edges_m%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(u%2C%20v)%3A%20model.new_bool_var(%22%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20u%20in%20indices_m%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20v%20in%20indices_m%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20u%20!%3D%20v%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20model.add_circuit((u%2C%20v%2C%20var)%20for%20(u%2C%20v)%2C%20var%20in%20edges_m.items())%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edges%20%7C%3D%20edges_m%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(u%2C%20v)%2C%20var%20in%20edges.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20u%20%3C%20-2%20or%20v%20%3C%20-2%3A%0A%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%20if%20u%20%3D%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20model.add(starts%5Bu%5D%20%3C%3D%20starts%5Bv%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20model.add(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20starts%5Bu%5D%20%2B%20all_tasks%5Bu%5D.time%20%3C%3D%20starts%5Bv%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20).only_enforce_if(edges%5B(u%2C%20v)%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20model.minimize(starts%5B-2%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.model%20%3D%20model%0A%20%20%20%20%20%20%20%20%20%20%20%20self.objective%20%3D%20starts%5B-2%5D%0A%0A%20%20%20%20%20%20%20%20def%20solve(self%2C%20timeout%3A%20int%20%3D%2010)%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(ModelCpSatArc%2C)%0A%0A%0A%40app.cell%0Adef%20_(ModelCpSatArc%2C%20jobs1%2C%20mo)%3A%0A%20%20%20%20model1_cpsatarc%20%3D%20ModelCpSatArc(jobs1)%0A%20%20%20%20model1_cpsatarc.solve()%0A%0A%20%20%20%20mo.md(f%22makespan%20%3D%20%7Bround(model1_cpsatarc.solver.objective_value)%7D%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ModelCpSatArc%2C%20jobs3%2C%20mo)%3A%0A%20%20%20%20model3_cpsatarc%20%3D%20ModelCpSatArc(jobs3)%0A%20%20%20%20model3_cpsatarc.solve(timeout%3D10)%0A%0A%20%20%20%20mo.md(f%22makespan%20%3D%20%7Bround(model3_cpsatarc.solver.objective_value)%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%E3%81%AA%E3%82%93%E3%81%8B%E5%85%A8%E7%84%B6%E3%83%80%E3%83%A1%E3%81%A0%E3%81%A3%E3%81%9F...%0A%0A%20%20%20%20%20%20%20%20%E5%8C%BA%E9%96%93%E5%A4%89%E6%95%B0%E3%82%88%E3%82%8A%20circuit%20constraint%20%E3%81%AE%E6%96%B9%E3%81%8C%E3%81%84%E3%81%84%E5%A0%B4%E5%90%88%E3%82%82%E3%81%82%E3%82%8B%E3%82%89%E3%81%97%E3%81%84%5B%5E1%5D%E3%81%8C%2C%20%E4%BB%8A%E5%9B%9E%E3%81%AF%E3%83%80%E3%83%A1%E3%81%9D%E3%81%86.%0A%0A%20%20%20%20%20%20%20%20%5B%5E1%5D%3A%20https%3A%2F%2Fd-krupke.github.io%2Fcpsat-primer%2F04B_advanced_modelling.html%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%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