Reference no: EM132209996
Question 1. Six jobs are to be scheduled on two machines. Each job j has an operationon machine MA requiring a processing time of aj and an operation on machineMBrequiring a processing time of bj. These processing times are shown in thefollowing table.
Job j
|
1
|
2
|
3
|
4
|
5
|
6
|
aj
|
6
|
5
|
2
|
1
|
10
|
3
|
bj
|
1
|
3
|
5
|
2
|
14
|
4
|
(i) Assuming an open shop environment where the two operations on each jobcan be executed in either order, find a schedule that minimizes the maximumcompletion time, i.e. solve problem O2||Cmax.
(ii) Assuming a flow shop environment where the operation on machine A mustprecede the operation on machine B for each job, find a schedule that minimizesthe maximum completion time, i.e. solve problem F2||Cmax.
Question 2. (i) Describe some desirable properties of heuristics that should be consideredwhen designing a heuristic for a problem.
(ii) Describe the furthest insertion heuristic for the symmetric travelling salesmanproblem.
(iii) Describe the main features of a tabu search algorithm.
Question 3. The owner of a chain of three gardening stores has obtained five lawnmowers,and has to decide how to allocate the lawnmowers to the stores. The followingtable shows the expected profit (in pounds) of allocating different numbers oflawnmowers to the different stores.
|
Number of lawnmowers allocated
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Store 1
|
0
|
60
|
110
|
155
|
170
|
180
|
Store 2
|
0
|
50
|
120
|
170
|
200
|
210
|
Store 3
|
0
|
55
|
110
|
150
|
185
|
195
|
The problem is to determine how many lawnmowers to allocate to each store tomaximize the total expected profit.
(i) Derive a recursive formula that is suitable for use in a dynamic programmingapproach.
(ii) Determine an optimal allocation of lawnmowers to stores so that the total expected profit is maximized.
Question 4. For the problem 1||∑wjCj of scheduling jobs on a single machine to minimizethe total weighted completion time, each job j becomes available for processingat time zero, requires a processing time of pj on the machine, and has a positiveweight wj. Show that the shortest weighted processing time (SWPT) rule yieldsan optimal solution.
Find the minimum total weighted completion time for the 7-job problem, where the processing times and weights are given in the following table.
Job j
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
pj
|
4
|
5
|
3
|
7
|
5
|
6
|
8
|
wj
|
3
|
6
|
2
|
5
|
4
|
3
|
5
|
Question 5. Consider a job shop in which there are three machines, and three jobs requireprocessing. The machine routing and the processing time for each operation on each job are shown in the table. The objective is to minimize the maximumcompletion of the jobs.
Job
|
Machine Routing
|
Processing Time
|
1
|
2
|
1
|
3
|
2
|
7
|
9
|
2
|
3
|
1
|
2
|
6
|
8
|
6
|
3
|
1
|
2
|
3
|
6
|
4
|
1
|
Using the most work remaining (MWKR) priority rule to decide between operations that require the same machine, generate an active schedule and find the maximum completion time of the three jobs.
Question 6. Suppose you work for Amazon Logistics, and your job today is to deliver 6 parcels to 6 different homes. You are asked to make a tour. You depart from local delivery centre A, visit each home (B, C, D, E, F, G) exactly once, and return to local delivery centre A. The distances between any two places are given in the table below.
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
A
|
-
|
8
|
14
|
12
|
13
|
11
|
8
|
B
|
8
|
-
|
9
|
10
|
9
|
11
|
11
|
C
|
13
|
9
|
-
|
7
|
11
|
10
|
10
|
D
|
11
|
11
|
9
|
-
|
10
|
10
|
10
|
E
|
14
|
9
|
11
|
14
|
-
|
9
|
11
|
F
|
12
|
10
|
14
|
10
|
7
|
-
|
13
|
G
|
8
|
11
|
11
|
13
|
10
|
10
|
-
|
(i) Use nearest neighbour method to make a tour, calculate the total distance travelled, and demonstrate each step in making such a tour.
(ii) Use furthest insertion method to make a tour, calculate the total distance travelled, and demonstrate each step in making such a tour.
Question 7. ReadyPlayerOne is an esports (a form of competition using video games) organisation. It now has the capacity to build a new professional team for an action role-playing game. A detailed analysis suggests that the two most popular games of this type are "Mount & Blade" and "For Honor". The annual profit the organisation expects depends on the long run popularity of such game type which can be low, medium, or high.
If ReadyPlayerOne chooses "Mount & Blade", the annual profit is expected to be $200,000, $250,000 and $300,000 for low, medium, and high popularity respectively. If ReadyPlayerOne chooses "For Honor", the annual profit is expected to be $150,000, $210,000, and $310,000 for low, medium, and high demand respectively.
(i) Formulate the organisation's situation as a decision analysis problem and determine the payoff matrix.
(ii) Which decisions would you take if you apply the optimistic, conservative, and minimax-regret approaches.
(iii) The organisation estimates that there is a 25% chance that the popularity will be low and a 50% chance that the popularity will be medium. Which decision would you recommend if the organisation's objective is to maximise the expected profit?
Question 8. Bertfordshire is a county which has two competing business schools "Hertfordshire Business School" and "Bedfordshire Business School". Both business schools have come up with a number of possible new courses to attract students.
The possible new courses for "Hertfordshire Business School" are to offer "Business Analytics with Statistics (BAS)" or "Supply Engineering and Logistics (SEL)". The options for "Bedfordshire Business School" are to offer "Management Science with Finance (MSF)", "International Business Studies (IBS)", or "Sensors and Smart Cities (SSC)".
In the next few years when "Hertfordshire Business School" offers "Business Analytics with Statistics (BAS)", they lose 30 students if "Bedfordshire Business School" offers "Management Science with Finance (MSF)", gain 100 students if "Bedfordshire Business School" offers "International Business Studies (IBS)", and lose 80 students if "Bedfordshire Business School" offers "Sensors and Smart Cities (SSC)".
In the next few years when "Hertfordshire Business School" offers "Supply Engineering and Logistics (SEL)", they gain 80 students if "Bedfordshire Business School" offers "Management Science with Finance (MSF)", gain 40 students if "Bedfordshire Business School" offers "International Business Studies (IBS)", and gain 50 students if "Bedfordshire Business School" offers "Sensors and Smart Cities (SSC)".
(i) Formulate this situation as a Game Theory problem.
(ii) Determine if there is a solution in pure strategy for this game.
(iii) Determine the best courses each school should offer to the students.
(iv) If both business schools deliver their best courses, how many students, on average, will each school gain or lose in a year?
Question 9. (i) Explain the factors to be considered when estimating the holding cost and the ordering or setup cost in an inventory control system.
(ii) The daily demand for birthday cakes in a supermarket has the following probability distribution.
Number of cakes
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
Probability
|
0.04
|
0.08
|
0.15
|
0.20
|
0.25
|
0.18
|
0.07
|
0.03
|
The supermarket pays £3 for each cake. Each cake that is sold produces£10 in revenue. Any cakes that are not sold to the supermarket's customers at the end of a day are sold at a reduced price of £1 per cake to the staff at the supermarket.
Analyse how many cakes the supermarket should buy each day.
Question 10. Passengers at an airport terminal must pass through a security screening machine before proceeding to the next area in the airport. Passengers join the queue following a Poisson process at a rate of 35 per hour. The average security screening duration is 1.5 minutes and follows an Exponential distribution. There is a single security screening machine in the terminal.
(i) Formulate the problem and determine if this system reaches a steady state.
(ii) A passenger has just arrived at the screening machine. What is the probability the passenger will have to wait before going through the screening machine? What is, therefore, the probability that the passenger will not wait before going through the screening machine.
(iii) What is the average number of passengers in the screening machine queue?
(iv) What is the average time spent by a passenger in the screening machine queue? What is, therefore, the average time spent by a passenger from the moment s/he joins the screening machine queue until the screening process is completed?
(v) The terminal manager is considering introducing a new security screening machine, which will change the distribution of the security screening duration from Exponential to Gamma distribution with a mean of 1.2 minutes and a standard deviation of 1 minute. Will the introduction of this new machine reduce the average time spent by a passenger in the screening machine queue?