Let's solve each question step by step, with explanations and final answers. --- ## **1. Non-identical Parallel Machine Scheduling Problem** ### **(a) Decision Variables** Given: - \( n \): Number of jobs - \( m \): Number of machines - \( X_{j,k,i} \): 1 if job \( j \) is assigned to position \( k \) on machine \( i \), 0 otherwise. **Define additional decision variables:** - \( C_j \): Completion time of job \( j \). **Explanation:** - \( X_{j,k,i} \): Binary variable indicating assignment. - \( C_j \): Continuous variable for the completion time of each job. --- ### **(b) Objective Function (Closed Form + Verbal Explanation)** **CLOSED FORM:** \[ \text{Minimize } Z = \sum_{j=1}^n C_j \] **Verbal Explanation:** - The objective is to minimize the total completion time, which is the sum of the completion times of all jobs. --- ### **(c) Constraints (Closed Form + Verbal Explanation)** #### **Assignment Constraints:** - Each job is assigned to exactly one position on one machine: \[ \sum_{k=1}^n \sum_{i=1}^m X_{j,k,i} = 1 \quad \forall j = 1,\ldots,n \] - Each position on each machine gets at most one job: \[ \sum_{j=1}^n X_{j,k,i} \leq 1 \quad \forall k = 1,\ldots,n;\ \forall i=1,\ldots,m \] #### **Completion Time Constraints:** Let \( p_{j,i} \): Processing time of job \( j \) on machine \( i \). - For each job, its completion time is at least the sum of processing times of jobs scheduled before it on the same machine: \[ C_j \geq \sum_{l=1}^n \sum_{k=1}^n p_{j,i} X_{j,k,i} \quad \forall j=1,\ldots,n;\ \forall i=1,\ldots,m \] #### **Binary and Non-negativity Constraints:** \[ X_{j,k,i} \in \{0,1\} \quad \forall j,k,i \] \[ C_j \geq 0 \quad \forall j \] **Verbal Explanation:** - Each job is assigned exactly once. - Each position on a machine is filled by at most one job. - The completion time is computed according to the schedule. - Variables are binary/non-negative as appropriate. --- ### **(d) MILP Model for Given Data (OPEN form)** #### **Given Data Table:** | Job | M1 | M2 | M3 | |------|----|----|----| | J1 | 4 | 8 | 6 | | J2 | 3 | 5 | 7 | | J3 | 6 | 7 | 3 | | J4 | 1 | 6 | 3 | | J5 | 7 | 4 | 6 | | J6 | 2 | 9 | 8 | | J7 | 4 | 5 | 7 | | J8 | 4 | 7 | 2 | | J9 | 8 | 2 | 5 | | J10 | 6 | 4 | 3 | #### **MILP Model (OPEN Form):** **Variables:** - \( X_{jki} \): 1 if job \( j \) is assigned to position \( k \) on machine \( i \), 0 otherwise, for \( j=1,\ldots,10; k=1,\ldots,10; i=1,2,3 \) - \( C_j \): Completion time of job \( j \) **Objective:** \[ \text{Minimize } \sum_{j=1}^{10} C_j \] **Constraints:** 1. **Each job assigned exactly once:** \[ \sum_{k=1}^{10} \sum_{i=1}^{3} X_{jki} = 1 \quad \forall j=1,\ldots,10 \] 2. **Each position on each machine has at most one job:** \[ \sum_{j=1}^{10} X_{jki} \leq 1 \quad \forall k=1,\ldots,10; \forall i=1,2,3 \] 3. **Completion time constraints:** \[ C_j \geq \sum_{k=1}^{10} \sum_{i=1}^{3} p_{ji} X_{jki} \quad \forall j=1,\ldots,10 \] (where \( p_{ji} \) is the processing time of job \( j \) on machine \( i \) from the table) 4. **Variable constraints:** \[ X_{jki} \in \{0,1\} \quad \forall j,k,i \] \[ C_j \geq 0 \quad \forall j \] --- ## **2. Cutting Stock Problem** ### **(a) Generate all feasible cutting patterns** Given: - Standard pipe length = 15 cm - Pipe lengths required: 3 cm (10 units), 5 cm (20 units), 8 cm (15 units) **Feasible patterns:** Let's denote pattern as (number of 3cm, 5cm, 8cm pipes cut from one 15cm pipe): - 5 × 3cm = 15cm → (5,0,0) - 3 × 3cm + 1 × 6cm = not possible (since we don’t have 6cm pipes) - 3 × 3cm + 1 × 5cm = 9 + 5 = 14cm (1cm waste) → (3,1,0) - 1 × 3cm + 2 × 5cm = 3 + 10 = 13cm (2cm waste) → (1,2,0) - 1 × 3cm + 1 × 5cm + 1 × 8cm = 3 + 5 + 8 = 16cm (not possible) - 1 × 3cm + 1 × 8cm = 3 + 8 = 11cm (4cm waste) - 1 × 5cm + 1 × 8cm = 5 + 8 = 13cm (2cm waste) - 1 × 8cm = 8cm (7cm waste) - 3 × 5cm = 15cm → (0,3,0) - 1 × 5cm + 2 × 3cm = 5 + 6 = 11cm (4cm waste) - 2 × 8cm = 16cm (not possible) - 1 × 3cm + 1 × 5cm + 1 × 8cm = 16cm (not possible) *Summary of feasible patterns:* 1. (5, 0, 0) 2. (3, 1, 0) 3. (1, 2, 0) 4. (0, 3, 0) 5. (0, 1, 1) 6. (1, 0, 1) 7. (0, 0, 1) --- ### **(b) Integer Programming Model (OPEN form)** **Variables:** - Let \( x_k \) = number of times pattern \( k \) is used, for all feasible patterns \( k \). **Objective:** - Minimize excess production of each pipe (let \( e_1, e_2, e_3 \) be excess of pipes 1, 2, 3). **Constraints:** - For each pipe type \( i \): \[ \sum_{k=1}^{K} a_{ik} x_k = d_i + e_i \quad \forall i = 1,2,3 \] where: - \( a_{ik} \) = number of pipe \( i \) in pattern \( k \) - \( d_i \) = demand for pipe \( i \) - \( e_i \geq 0 \) (excess pipes) **Variables:** - \( x_k \geq 0 \), integer (number of times pattern \( k \) is used) - \( e_i \geq 0 \), integer (excess pipes) **Minimize:** \[ Z = e_1 + e_2 + e_3 \] --- ## **3. Network Problems** ### **(a) Shortest Path Mathematical Model** **Variables:** - \( x_{ij} \): 1 if arc (i,j) is on the path, 0 otherwise **Objective:** \[ \text{Minimize } \sum_{(i,j) \in A} d_{ij} x_{ij} \] where \( d_{ij} \) is the distance between city \( i \) and city \( j \). **Constraints:** - **Flow constraints:** - From City 1 (source): \( \sum_{j} x_{1j} - \sum_{i} x_{i1} = 1 \) - To City 10 (sink): \( \sum_{i} x_{i10} - \sum_{j} x_{10j} = 1 \) - All other nodes: \( \sum_{j} x_{kj} - \sum_{i} x_{ik} = 0 \) for all other cities \( k \) - \( x_{ij} \in \{0,1\} \) --- ### **(b) Total Enumeration Approach** - List all possible paths from City 1 to City 10. - Calculate the total distance for each path. - Choose the path with the smallest total distance. --- ### **(c) Reduced Network** - Remove nodes not on any shortest path without breaking connections. - Redraw the network. - Use the same shortest path model as in (a) but on the reduced network. --- ### **(d) Communication System Model** - **Steiner Tree Problem** (Interconnecting all distributors with minimum total length). - Objective: Minimize the sum of distances to connect all nodes. - Decision variables: \( y_{ij} \) = 1 if arc (i,j) is included, 0 otherwise. --- ### **(e) Maximum Flow Problem** - **Max-flow problem** (from City 1 to City 10). - Variables: \( f_{ij} \): flow on arc (i,j) - Objective: Maximize total flow from City 1 to City 10. - Constraints: - Flow conservation at each node (except source and sink). - Flow on each arc \( \leq \) arc capacity. - Flows \( \geq 0 \). --- **If you need detailed step-by-step calculations for each part (like enumerating all paths for Q3 or listing all patterns for Q2), let me know!**