23-Ind-A1 Operations Research · December 2018
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
National Exams — December 2018 — 17-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 170 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming, the simplex method & sensitivity analysis/duality (ch. 3–4/6), integer programming & branch and bound (ch. 12), queueing theory (ch. 17), decision analysis (ch. 15), computer simulation (ch. 20). Nahmias, Production and Operations Analysis — single-period (newsvendor) and multi-period (dynamic lot-sizing / Wagner–Whitin) inventory models.
Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.
Given. 5 jobs, 5 candidate machines; a job can only run on a machine with a listed (non "–") processing time; each machine used incurs a one-time setup:
| Machine | Job 1 | Job 2 | Job 3 | Job 4 | Job 5 | Setup |
|---|---|---|---|---|---|---|
| 1 | 42 | 70 | 93 | – | – | 30 |
| 2 | – | 85 | 45 | – | – | 40 |
| 3 | 58 | – | – | 37 | – | 50 |
| 4 | 58 | – | 55 | – | 38 | 60 |
| 5 | – | 60 | – | 54 | – | 20 |
Find. An integer program that assigns each job to a feasible machine and decides which machines to set up, minimizing total processing plus setup time (formulate only, do not solve).
Approach. This is a generalized assignment problem with a fixed-charge (setup) cost per machine actually used: define a binary assignment variable per feasible (machine, job) pair and a binary "machine used" variable, then link them so a setup is only charged when the machine is actually assigned at least one job.
Decision variables. Let $F=\{(i,j): \text{machine }i\text{ can process job }j\}$ be the 12 feasible pairs shown in the table ($(1,1),(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(4,1),(4,3),(4,5),(5,2),(5,4)$). Let $t_{ij}$ = processing time and $u_i$ = setup time (from the table). Define $x_{ij}\in\{0,1\}$ = 1 if job $j$ is assigned to machine $i$ (only for $(i,j)\in F$), and $y_i\in\{0,1\}$ = 1 if machine $i$ is used (set up) at all.
$$\boxed{\min Z=\sum_{(i,j)\in F} t_{ij}\,x_{ij}\ +\ \sum_{i=1}^{5} u_i\,y_i}$$subject to:
$$\text{Every job assigned exactly once:}\quad \sum_{i:(i,j)\in F} x_{ij}=1\qquad \text{for each job } j=1,\dots,5$$ $$\text{Setup triggered by use:}\quad x_{ij}\le y_i\qquad \text{for every }(i,j)\in F$$ $$x_{ij}\in\{0,1\}\ \ \forall (i,j)\in F,\qquad y_i\in\{0,1\}\ \ \forall i=1,\dots,5$$