Crew assignment problem calculator

SolutionHelp

Solution

Solution provided by AtoZmath.com

1. Best-ride airlines that operates seven days a week has the following time-table.

Delhi - Mumbai

Mumbai - Delhi

Flight No	Departure	Arrival
1	7.00	8.00
2	8.00	9.00
3	13.00	14.00
4	18.00	19.00

Flight No	Departure	Arrival
101	8.00	9.00
102	9.00	10.00
103	12.00	13.00
104	17.00	18.00

Crews must have a minimum layover of 5 hours between flights. Obtain the pairing of flights that minimizes layover time away from home. For any given pairing, the crew will be based at the city that results in the smaller layover. For each pair also mention the city where crew should be based.

Example

1. Crew assignment problem
Delhi - Mumbai Mumbai - Delhi
Flight No Departure Arrival
1 7.00 8.00
2 8.00 9.00
3 13.00 14.00
4 18.00 19.00
Flight No Departure Arrival
101 8.00 9.00
102 09.00 10.00
103 12.00 13.00
104 17.00 18.00

Minimum layover of hours between flights : 5

Solution:
To determine optimal assignments, first we calculate layover times from the above time table.
Calculating values for table 1 (layover time)
`1^(st)` Row

Cell-`1` Arrival time (Mumbai) = 08:00, Departure time (Mumbai) = 08:00, Waiting time (difference) = 24

Cell-`2` Arrival time (Mumbai) = 08:00, Departure time (Mumbai) = 09:00, Waiting time (difference) = 25

Cell-`3` Arrival time (Mumbai) = 08:00, Departure time (Mumbai) = 12:00, Waiting time (difference) = 28

Cell-`4` Arrival time (Mumbai) = 08:00, Departure time (Mumbai) = 17:00, Waiting time (difference) = 9

`2^(nd)` Row

Cell-`1` Arrival time (Mumbai) = 09:00, Departure time (Mumbai) = 08:00, Waiting time (difference) = 23

Cell-`2` Arrival time (Mumbai) = 09:00, Departure time (Mumbai) = 09:00, Waiting time (difference) = 24

Cell-`3` Arrival time (Mumbai) = 09:00, Departure time (Mumbai) = 12:00, Waiting time (difference) = 27

Cell-`4` Arrival time (Mumbai) = 09:00, Departure time (Mumbai) = 17:00, Waiting time (difference) = 8

`3^(rd)` Row

Cell-`1` Arrival time (Mumbai) = 14:00, Departure time (Mumbai) = 08:00, Waiting time (difference) = 18

Cell-`2` Arrival time (Mumbai) = 14:00, Departure time (Mumbai) = 09:00, Waiting time (difference) = 19

Cell-`3` Arrival time (Mumbai) = 14:00, Departure time (Mumbai) = 12:00, Waiting time (difference) = 22

Cell-`4` Arrival time (Mumbai) = 14:00, Departure time (Mumbai) = 17:00, Waiting time (difference) = 27

`4^(th)` Row

Cell-`1` Arrival time (Mumbai) = 19:00, Departure time (Mumbai) = 08:00, Waiting time (difference) = 13

Cell-`2` Arrival time (Mumbai) = 19:00, Departure time (Mumbai) = 09:00, Waiting time (difference) = 14

Cell-`3` Arrival time (Mumbai) = 19:00, Departure time (Mumbai) = 12:00, Waiting time (difference) = 17

Cell-`4` Arrival time (Mumbai) = 19:00, Departure time (Mumbai) = 17:00, Waiting time (difference) = 22

Table-1 : Crew based at Delhi

	`101`	`102`	`103`	`104`
`1`	24 Cell-`1` Arrival time (Mumbai) = 08:00, Departure time (Mumbai) = 08:00, Waiting time (difference) = 24	25 Cell-`2` Arrival time (Mumbai) = 08:00, Departure time (Mumbai) = 09:00, Waiting time (difference) = 25	28 Cell-`3` Arrival time (Mumbai) = 08:00, Departure time (Mumbai) = 12:00, Waiting time (difference) = 28	9 Cell-`4` Arrival time (Mumbai) = 08:00, Departure time (Mumbai) = 17:00, Waiting time (difference) = 9
`2`	23 Cell-`1` Arrival time (Mumbai) = 09:00, Departure time (Mumbai) = 08:00, Waiting time (difference) = 23	24 Cell-`2` Arrival time (Mumbai) = 09:00, Departure time (Mumbai) = 09:00, Waiting time (difference) = 24	27 Cell-`3` Arrival time (Mumbai) = 09:00, Departure time (Mumbai) = 12:00, Waiting time (difference) = 27	8 Cell-`4` Arrival time (Mumbai) = 09:00, Departure time (Mumbai) = 17:00, Waiting time (difference) = 8
`3`	18 Cell-`1` Arrival time (Mumbai) = 14:00, Departure time (Mumbai) = 08:00, Waiting time (difference) = 18	19 Cell-`2` Arrival time (Mumbai) = 14:00, Departure time (Mumbai) = 09:00, Waiting time (difference) = 19	22 Cell-`3` Arrival time (Mumbai) = 14:00, Departure time (Mumbai) = 12:00, Waiting time (difference) = 22	27 Cell-`4` Arrival time (Mumbai) = 14:00, Departure time (Mumbai) = 17:00, Waiting time (difference) = 27
`4`	13 Cell-`1` Arrival time (Mumbai) = 19:00, Departure time (Mumbai) = 08:00, Waiting time (difference) = 13	14 Cell-`2` Arrival time (Mumbai) = 19:00, Departure time (Mumbai) = 09:00, Waiting time (difference) = 14	17 Cell-`3` Arrival time (Mumbai) = 19:00, Departure time (Mumbai) = 12:00, Waiting time (difference) = 17	22 Cell-`4` Arrival time (Mumbai) = 19:00, Departure time (Mumbai) = 17:00, Waiting time (difference) = 22

Calculating values for table 2 (layover time)
`1^(st)` Column

Cell-`1` Arrival time (Delhi) = 09:00, Departure time (Delhi) = 07:00, Waiting time (difference) = 22

Cell-`2` Arrival time (Delhi) = 10:00, Departure time (Delhi) = 07:00, Waiting time (difference) = 21

Cell-`3` Arrival time (Delhi) = 13:00, Departure time (Delhi) = 07:00, Waiting time (difference) = 18

Cell-`4` Arrival time (Delhi) = 18:00, Departure time (Delhi) = 07:00, Waiting time (difference) = 13

`2^(nd)` Column

Cell-`1` Arrival time (Delhi) = 09:00, Departure time (Delhi) = 08:00, Waiting time (difference) = 23

Cell-`2` Arrival time (Delhi) = 10:00, Departure time (Delhi) = 08:00, Waiting time (difference) = 22

Cell-`3` Arrival time (Delhi) = 13:00, Departure time (Delhi) = 08:00, Waiting time (difference) = 19

Cell-`4` Arrival time (Delhi) = 18:00, Departure time (Delhi) = 08:00, Waiting time (difference) = 14

`3^(rd)` Column

Cell-`1` Arrival time (Delhi) = 09:00, Departure time (Delhi) = 13:00, Waiting time (difference) = 28

Cell-`2` Arrival time (Delhi) = 10:00, Departure time (Delhi) = 13:00, Waiting time (difference) = 27

Cell-`3` Arrival time (Delhi) = 13:00, Departure time (Delhi) = 13:00, Waiting time (difference) = 24

Cell-`4` Arrival time (Delhi) = 18:00, Departure time (Delhi) = 13:00, Waiting time (difference) = 19

`4^(th)` Column

Cell-`1` Arrival time (Delhi) = 09:00, Departure time (Delhi) = 18:00, Waiting time (difference) = 9

Cell-`2` Arrival time (Delhi) = 10:00, Departure time (Delhi) = 18:00, Waiting time (difference) = 8

Cell-`3` Arrival time (Delhi) = 13:00, Departure time (Delhi) = 18:00, Waiting time (difference) = 29

Cell-`4` Arrival time (Delhi) = 18:00, Departure time (Delhi) = 18:00, Waiting time (difference) = 24

Table-2 : Crew based at Mumbai

	`101`	`102`	`103`	`104`
`1`	22 Cell-`1` Arrival time (Delhi) = 09:00, Departure time (Delhi) = 07:00, Waiting time (difference) = 22	21 Cell-`2` Arrival time (Delhi) = 10:00, Departure time (Delhi) = 07:00, Waiting time (difference) = 21	18 Cell-`3` Arrival time (Delhi) = 13:00, Departure time (Delhi) = 07:00, Waiting time (difference) = 18	13 Cell-`4` Arrival time (Delhi) = 18:00, Departure time (Delhi) = 07:00, Waiting time (difference) = 13
`2`	23 Cell-`1` Arrival time (Delhi) = 09:00, Departure time (Delhi) = 08:00, Waiting time (difference) = 23	22 Cell-`2` Arrival time (Delhi) = 10:00, Departure time (Delhi) = 08:00, Waiting time (difference) = 22	19 Cell-`3` Arrival time (Delhi) = 13:00, Departure time (Delhi) = 08:00, Waiting time (difference) = 19	14 Cell-`4` Arrival time (Delhi) = 18:00, Departure time (Delhi) = 08:00, Waiting time (difference) = 14
`3`	28 Cell-`1` Arrival time (Delhi) = 09:00, Departure time (Delhi) = 13:00, Waiting time (difference) = 28	27 Cell-`2` Arrival time (Delhi) = 10:00, Departure time (Delhi) = 13:00, Waiting time (difference) = 27	24 Cell-`3` Arrival time (Delhi) = 13:00, Departure time (Delhi) = 13:00, Waiting time (difference) = 24	19 Cell-`4` Arrival time (Delhi) = 18:00, Departure time (Delhi) = 13:00, Waiting time (difference) = 19
`4`	9 Cell-`1` Arrival time (Delhi) = 09:00, Departure time (Delhi) = 18:00, Waiting time (difference) = 9	8 Cell-`2` Arrival time (Delhi) = 10:00, Departure time (Delhi) = 18:00, Waiting time (difference) = 8	29 Cell-`3` Arrival time (Delhi) = 13:00, Departure time (Delhi) = 18:00, Waiting time (difference) = 29	24 Cell-`4` Arrival time (Delhi) = 18:00, Departure time (Delhi) = 18:00, Waiting time (difference) = 24

The composite layover time matrix (Table-3) is obtained by selecting the smaller element from the two corresponding elements of Table-1 and Table-2. The layover time marked with (*) represents that the crew is based at Mumbai, otherwise based at Delhi.
Table-3

	`101`	`102`	`103`	`104`
`1`	`22^**` Crew based at Mumbai (Table-2) `22="Min"{24,22}`	`21^**` Crew based at Mumbai (Table-2) `21="Min"{25,21}`	`18^**` Crew based at Mumbai (Table-2) `18="Min"{28,18}`	`9` Crew based at Delhi (Table-1) `9="Min"{9,13}`
`2`	`23^**` Crew based at Mumbai (Table-2) `23="Min"{23,23}`	`22^**` Crew based at Mumbai (Table-2) `22="Min"{24,22}`	`19^**` Crew based at Mumbai (Table-2) `19="Min"{27,19}`	`8` Crew based at Delhi (Table-1) `8="Min"{8,14}`
`3`	`18` Crew based at Delhi (Table-1) `18="Min"{18,28}`	`19` Crew based at Delhi (Table-1) `19="Min"{19,27}`	`22` Crew based at Delhi (Table-1) `22="Min"{22,24}`	`19^**` Crew based at Mumbai (Table-2) `19="Min"{27,19}`
`4`	`9^**` Crew based at Mumbai (Table-2) `9="Min"{13,9}`	`8^**` Crew based at Mumbai (Table-2) `8="Min"{14,8}`	`17` Crew based at Delhi (Table-1) `17="Min"{17,29}`	`22` Crew based at Delhi (Table-1) `22="Min"{22,24}`

Now the above problem can be easily solved by Hungarian method.

Step-1: Find out the each row minimum element and subtract it from that row

	`101`	`102`	`103`	`104`
`1`	13 `13=22-9`	12 `12=21-9`	9 `9=18-9`	0 `0=9-9`	(-9)
`2`	15 `15=23-8`	14 `14=22-8`	11 `11=19-8`	0 `0=8-8`	(-8)
`3`	0 `0=18-18`	1 `1=19-18`	4 `4=22-18`	1 `1=19-18`	(-18)
`4`	1 `1=9-8`	0 `0=8-8`	9 `9=17-8`	14 `14=22-8`	(-8)

Step-2: Find out the each column minimum element and subtract it from that column.

	`101`	`102`	`103`	`104`
`1`	13 `13=13-0`	12 `12=12-0`	5 `5=9-4`	0 `0=0-0`
`2`	15 `15=15-0`	14 `14=14-0`	7 `7=11-4`	0 `0=0-0`
`3`	0 `0=0-0`	1 `1=1-0`	0 `0=4-4`	1 `1=1-0`
`4`	1 `1=1-0`	0 `0=0-0`	5 `5=9-4`	14 `14=14-0`
	(-0)	(-0)	(-4)	(-0)

Step-3: Make assignment in the opporunity cost table

(a) Examine rows successively unitl a row with exactly one unmarked 0 is obtained. Make an assignmment to this single 0 by make a square ( [0] ) around it.
(b) For each 0 value that becomes assigned, eliminate (strike off) all other 0 in the same row and/or column.
(c) Repeat steps 3(a) and 3(b) for each column also with exactly single 0 value cell that has not been assigned or eliminated.
(d) If a row and/or column has two or more unmarked 0 and one cannot be chosen by inspection, then choose the assigned 0 cell arbitarily
(e) Continue this process until all 0 in rows/columns are either enclosed (assigned) or strike off(

)

Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(1,104)` is assigned, so columnwise cell `(2,104)` crossed off.

(2) Rowwise cell `(4,102)` is assigned

(3) Columnwise cell `(3,101)` is assigned, so rowwise cell `(3,103)` crossed off.

Rowwise & columnwise assignment shown in table

	`101`	`102`	`103`	`104`
`1`	13	12	5	[0] (1) Rowwise cell `(1,104)` is assigned so columnwise cell `(2,104)` crossed off.
`2`	15	14	7	0 Columnwise `(2,104)` crossed off because (1) Rowwise cell `(1,104)` is assigned
`3`	[0] (3) Columnwise cell `(3,101)` is assigned so rowwise cell `(3,103)` crossed off.	1	0 Rowwise `(3,103)` crossed off because (3) Columnwise cell `(3,101)` is assigned	1
`4`	1	[0] (2) Rowwise cell `(4,102)` is assigned	5	14

Step-4: Number of assignments = 3, number of rows = 4
Which is not equal, so solution is not optimal.

Step-5: Cover the 0 with minimum number of lines

Draw a set of horizontal and vertical lines to cover all the 0
(a) For each row in which no assignment was made, mark a tick(✓)
(b) Examine the marked rows. If any 0 cell occurs in those rows, mark a ✓ to the respective columns that cotain those 0.
(c) Examine marked columns. If any assigned 0 occurs in those columns, then tick the respective rows that contain those assigned 0.
(d) Repeat this process until no more rows or columns can be marked.
(e) Draw a straight line through each marked column and each unmarked row.
If the number of lines drawn(or total assignment) is equal to the number of rows (or columns) then the current solution is the optimal solution, otherwise goto step-6

Step-5: Cover the 0 with minimum number of lines
(1) Mark(✓) row `2` since it has no assignment

(2) Mark(✓) column `104` since row `2` has 0 in this column

(3) Mark(✓) row `1` since column `104` has an assignment in this row `1`.

(4) Since no other rows or columns can be marked, therefore draw straight lines through the unmarked rows `3,4` and marked columns `104`

Tick mark not allocated rows and allocated columns

	`101`	`102`	`103`	`104`
`1`	13	12	5	[0]	✓(3) (3) Mark(✓) row `1` since column `104` has an assignment in this row `1`.
`2`	15	14	7	0	✓(1) (1) Mark(✓) row `2` since it has no assignment
`3`	[0]	1	0	1
`4`	1	[0]	5	14
				✓ (2) (2) Mark(✓) column `104` since row `2` has 0 in this column

Step-6: Develop the new revised opportunity cost table

(a) From among the cells not covered by any line, choose the smallest element, say k
(b) Subtract k from every element in the cell not covered by a line.
(c) Add k to every elment in the intersection cell of two lines.
(d) Elements in cells covered by one line remains unchanged.

Step-6: Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 5)
Subtract k = 5 from every element in the cell not covered by a line.
Add k = 5 to every elment in the intersection cell of two lines.

	`101`	`102`	`103`	`104`
`1`	8 `8=13-5` cell not covered by a line	7 `7=12-5` cell not covered by a line	0 `0=5-5` cell not covered by a line	0 cell covered by a line
`2`	10 `10=15-5` cell not covered by a line	9 `9=14-5` cell not covered by a line	2 `2=7-5` cell not covered by a line	0 cell covered by a line
`3`	0 cell covered by a line	1 cell covered by a line	0 cell covered by a line	6 `6=1+5` intersection cell of two lines
`4`	1 cell covered by a line	0 cell covered by a line	5 cell covered by a line	19 `19=14+5` intersection cell of two lines

Repeat steps 3 to 6 until an optimal solution is obtained.

Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(2,104)` is assigned, so columnwise cell `(1,104)` crossed off.

(2) Rowwise cell `(4,102)` is assigned

(3) Columnwise cell `(3,101)` is assigned, so rowwise cell `(3,103)` crossed off.

(4) Columnwise cell `(1,103)` is assigned

Rowwise & columnwise assignment shown in table

	`101`	`102`	`103`	`104`
`1`	8	7	[0] (4) Columnwise cell `(1,103)` is assigned	0 Columnwise `(1,104)` crossed off because (1) Rowwise cell `(2,104)` is assigned
`2`	10	9	2	[0] (1) Rowwise cell `(2,104)` is assigned so columnwise cell `(1,104)` crossed off.
`3`	[0] (3) Columnwise cell `(3,101)` is assigned so rowwise cell `(3,103)` crossed off.	1	0 Rowwise `(3,103)` crossed off because (3) Columnwise cell `(3,101)` is assigned	6
`4`	1	[0] (2) Rowwise cell `(4,102)` is assigned	5	19

Step-4: Number of assignments = 4, number of rows = 4
Which is equal, so solution is optimal

Optimal assignments are

	`101`	`102`	`103`	`104`
`1`	8 Original cost 22	7 Original cost 21	[0] Original cost 18	0 Original cost 9
`2`	10 Original cost 23	9 Original cost 22	2 Original cost 19	[0] Original cost 8
`3`	[0] Original cost 18	1 Original cost 19	0 Original cost 22	6 Original cost 19
`4`	1 Original cost 9	[0] Original cost 8	5 Original cost 17	19 Original cost 22

Optimal solution is

Work	Job	Cost
`1`	`103`	18
`2`	`104`	8
`3`	`101`	18
`4`	`102`	8
	Total	52