Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 33 / 5

The total processing time ${\sum }_{i=1}^{40}{t}_i$ is constant for a single machine, so only the initial setup and changeover sum depends on the order. Use the dummy-job reduction for sequence-dependent setup times. Add vertex $0$, and setLet the binary variable $x_{ij}$ indicate that $j$ follows $i$ in the augmented tour. A Hamiltonian cycle through $0$ specifies exactly one schedule, read starting after $0$. An exact integer programming formulation isThe degree equations alone describe a cycle cover of a directed graph, possibly several separate graph cycles. The subtour elimination constraints exclude every proper directed graph cycle; the cover is therefore a single tour through all jobs. Conversely every schedule supplies a feasible tour with exactly its completion time as objective. Exponentially many written inequalities are permitted in this exact formulation; an implementation may add them only when violated.

For three parallel machines, the relevant objective is the parallel-machine makespan with sequence-dependent setups, not simply total setup cost. Partition jobs into three ordered lists ${\pi }_r$. For a nonempty list definean empty machine has $C_r=0$. Minimize $C_{\max }$ subject to $C_r\le C_{\max }$ for each machine and each job assigned once. This can be written as a mixed-integer extension with assignment variables, one dummy tour per machine and conditional subtour cuts.

A practical strategy starts with a balanced assignment, sequences each machine using the single-machine methods, and improves by relocating or swapping jobs between machines together with within-machine 2-opt moves. Score each move by its change in ${\max }_r{C}_r$. Branch and bound can combine machine-assignment decisions with within-machine assignment bounds. For nonnegative times, the total processing time divided by three and the largest individual processing time are valid lower bounds, supplemented by setup-dependent route bounds. Balancing processing and changeovers jointly is essential; independently minimizing the three tour costs does not by itself minimize completion time.

Drop the subtour elimination constraints, retaining the one-incoming/one-outgoing equations and any branch decisions. This is an assignment problem, solvable in polynomial time. Its optimum is a lower bound on the best schedule in that branch because every admissible schedule satisfies the relaxed constraints. Add the constant processing-time sum to compare completion-time bounds.

Keep a feasible schedule as an incumbent upper bound. At each branch and bound node, solve the restricted assignment problem. If it is infeasible or its bound is at least the incumbent, discard the node. If its optimum is a single tour, it is a feasible schedule attaining the bound, so update the incumbent and close the node. If it has a proper subtour $C$ with arcs $e_1,\dots ,e_r$, every valid Hamiltonian tour must omit at least one of those arcs.

For a disjoint exhaustive branching rule, child $h$ forces $e_1,\dots ,e_{h-1}$ and forbids $e_h$, for $h=1,\dots ,r$. Every valid tour falls into the child indexed by the first omitted arc. Re-solve the corresponding assignment relaxations, prioritize small bounds, and repeat. Finitely many binary choices give an exact terminating search; its worst-case tree can be exponential. Assignment optima provide lower bounds, while complete tours provide upper bounds. Patching subtours or local improvement can improve the incumbent without changing the exact pruning argument.

Represent a schedule by a permutation $v_1,\dots ,v_{40}$, with $v_0=v_{41}=0$. Choose $1\le p<q\le 40$ and reverse the block $v_p,\dots ,v_q$. This is a 2-opt move on the dummy tour. Its exact setup-cost change is the asymmetric 2-opt reversal costThe internal sum matters because the specified changeovers need not be symmetric. When the block begins at the first job, the boundary terms correctly update the initial setup; the dummy return costs are zero. Processing times cancel.

At temperature $T>0$, simulated annealing accepts a move with probabilityWith uniformly sampled reversal pairs the proposal is symmetric, so this is the appropriate Metropolis–Hastings acceptance probability. Improvements and ties are always accepted; occasional uphill moves escape local minima. Repeatedly sample moves, gradually lower $T$, and retain the best schedule seen even if the current schedule worsens. Reversing a block of length two swaps adjacent jobs, so these moves connect the whole permutation space. A cooling schedule, iteration budget and restarts control practical performance. This is a heuristic at a finite budget; it does not certify global optimality unless paired with an exact bound or an appropriate limiting convergence argument.