MUO $-$ Solutions

MUO $-$ Solutions

$2$ Job$-$Shop Scheduling $[23$ pts$]$

You are an Al engineer responsible for job$-$shop schedul ing in a manufacturing company. You are required to assign five jobs $,$ and $\{$:$J_5)$ to two machines and $\{$:$M_2)$ over four time slots $,$ and $\{$:$T_4)$ Your manager as a successful AIN$2001$ graduate wants you to formulate this problem as a constraint satisfac tion problem $($CSP$).$ Your manager also provides the following information:

A machine over a time slot can be allocated to only one job.

Each job takes one time slot to be finished in a machine.

Some parts required for $J_1$ and $J_2$ will arrive at the end of time slot $T_1.$

$J_2$ and $J_4$ must be done in machine $M_1.$

$J_3$ and $J_5$ must be done in machine $M_2.$

$J_1$ and $J_3$ are pre$-$requisites for $J_4.$

$J_2$ and $J_4$ are pre$-$requisites for $J_5.$

$2\mathrm{.}1$ Problem formulation $[8$ pts$]$

Given the variables and domains below, please complete the CSP formulation by writing the constraints. Constraints must be expressed implicitly using mathematical or logical notation rather than with words.

Variables: $J_i=(m_{J_i},t_{J_i})$ where $i=1,$cdots,$5,$ for each area.

Domains: $AAi{J}_{i}in\{\begin{array}{ccc}{m}_{J_i},& t_{J_i})|m_{J_i}in\{1,& 2\end{array}$ and $\{$:$t_{J_i}in\{1,2,3,4\}\}$

Constraints:

Unary constraints:

$t_{J_1}>1$

$t_{J_2}>1$

$m_{J_2}=1$

$m_{J_3}=2$

$m_{J_4}=1$

Binary constraints:

$m_{J_5}=2$

$2\mathrm{.}2$ Forward$-$checking with MRV $[15$ pts$]$

Starting with reduced domains of variables obtained after node$-$consistency, please perform forward$-$checking search using minimum$-$remaining$-$values $($MRV$)$ heuristic for variable selection and the lowest value first for value selection. In case of a tie in variable selection, please break the tie by picking the lower values first.

Please complete the below table by indicating the current level in the search tree $($L$),$ the reduced domains of variables, selected variable and value $($i$.$e$,$ the assignment $-$ A$),$ and the level we need to go back $($B$2$L$)$ if we need to change any of previous variable assignments.

$\backslash$table$[[$L$,J_1,J_2,J_3,J_4,J_5,$A$,$B$2$L$],[0,\backslash$table$[[,],[(2,2),(2,3),(2,4)$