MC 2014-15: PGP I/PGP-ABM I
MC Individual Assignment-II
Release Date: 19-8-14 Submission Date and Time 04-09-14, 6:00 PM

Instructions 1. This is an individual assignment (not group). 2. You are required to develop VBA solutions to the following two problems and submit the solutions as a single xlsm file on Moodle. 3. Your solution must be as general as possible – clearly state all assumptions. The VBA code must be neat, and well documented (introducing appropriate comments) 4. Submit your assignment file on Moodle well on time to avoid system congestions or break-downs during the last minute

Problem 1: Tourist spots in London
As a tourist in London you want to visit 7 spots and minimize the time spent on visiting these 7 spots. The details of the 7 spots including their ID, time to see the attraction, and opening time are given to you (Range A3:D9 in given spreadsheet).
Note that you want to visit each spot only once.
Range B13:H19 in the given spreadsheet contains the travel time (in minutes) between any two spots, 9999 stands for infinity. For example: travel from 2 to 5 (Trafalgar Square to Tower Bridge) takes 22 minutes. You can assume that all other times (wait times for transport, queues for attractions etc, are already accounted for in the sightseeing time and travel time).
The subroutine calc_schedule uses this information to calculate the route to be taken from the starting spot (given in G3) at the starting time given in G4.
The subroutine prints out the route below the travel table (skipping one row to maintain readability) and in the next row, the respective times that you will reach each spot. In-case, the heuristic cannot find a solution, an error message is printed on the spreadsheet.
The following ranges on the spreadsheet have been named as follows:
A3:D9 - spots_tbl
B13:H19 - travel_tbl
G3 - start
G4 - start_time

The algorithm to find the route is a greedy heuristic as follows : 1) From current spot, find the next spot (not yet seen) that can be reached with least travel time 2) If the travel time to all spots is infinity, then go to step 6. 3) Calculate when that spot will be reached (after accounting for sightseeing time at current spot and travel time to next spot) 4) If you will reach the next spot after it has opened, then continue to step 5.
Otherwise : 4.1 Mark travel time to this spot as infinity 4.2 Go to step 1 to find the next best option for next spot. 5) If all spots have been reached, then go to step 6, else go to step 1. 6) Stop

Write the VBA code for sub-routine calc_schedule as explained above.

Problem : 2 Scheduling n independent tasks on m identical machines
Consider a set of n tasks ( or Jobs), where n is given, with each task-j, j = 1, 2, …, n, having a given processing time t(j). A task can be processed on any of the m identical processors (or machines), where m is given. The tasks are to be assigned to the processors such that the make-span of the processing (that is, the time at which the entire set of jobs is finished, assuming that the time of starting the schedule is zero) is minimized. A machine cannot process more than one task at a time, and a task can be assigned to only one machine, and on that machine it has to be processed without any breaks in its processing.
A heuristic called longest processing time first (LPT) can be used for the above problem as below:
Initially all machines are free (or available). None of the tasks is scheduled.
From among the tasks still unscheduled, choose the one with the longest processing time, and assign it to the machine which is available at the earliest. In case of ties, the task which occurs first in the input list is taken, and the machine with the smallest index, if more than one is available at the same time, is chosen. The task that is chosen is scheduled on the machine that is chosen, beginning from the time at which the machine is available. The time at which the chosen machine becomes free after processing the chosen task is computed.
The above process is repeated till all the tasks are scheduled.
To illustrate the above heuristic, consider a 5-task, 2-machine problem with the following task list:

Task ID | Processing time | 5 | 6 | 2 | 10 | 1 | 15 | 3 | 12 | 4 | 20 |

In LPT, the first task to be considered is the task with longest processing time, which happens to be the task with ID 4 (call it task-4); hence task-4 is scheduled on machine-1 from 0 to 20.
The next task chosen would be task-1 with a processing time of 15; at this point in the process of scheduling, machine-1 will be available only at 20, whereas machine-2 at zero. Hence, task-1 is scheduled on machine-2 from zero to 15. Machine-2 is now available at 15.
The next task to be considered is task-3 with a processing time of 12. Machine-1 is busy till 20, and machine-2 till 15. As machine-2 becomes available first, task-3 is scheduled on machine-2 from 15 to 27.

The next task chosen would be task-2, with a processing time of 10. Of the two machines, machine-1 becomes available at 20 and machine-2 at 27. Hence task-2 is scheduled on machine-1 from 20 to 30.
The only remaining task is task-5, which has a processing time of 6. Machine-2 becomes available earlier than machine-1; hence, task-5 is scheduled on machine-2 from 27 to 33.
Thus, the LPT heuristic develops the schedule in which the sequence of task IDs for machine-1 is 4 2, and that for machine-2 is 135. It is easy to see that the task that finishes last in the above schedule is task-5, which finishes at 33; hence, the make span of the schedule is 33.
Given below is the listing of a VBA array-function named lpt, that implements the above heuristic.
The function is to be invoked from a spread sheet with two parameters: the first is a number, m (or a reference to a cell containing a number), that denotes the number of machines in the problem; the second is a range name, or range address referring to a range with two columns and number of rows equal to number of tasks; the first column contains the ID of each job (assume that a task ID is an integer), and the second contains the corresponding processing time.
For invoking the function lpt, highlight a range with number of rows = m, and the number of columns equal to n+2, and then type in the first cell =lpt with appropriate parameters in parentheses. The output consists of the schedule for the machines, one row for each machine respectively; the first n columns of a row show the job sequence assigned to the corresponding machine, the unused sequential positions filled with zeroes. (n+1)th column shows how many taks have been assigned to the machine; and (n+2) th column shows the time at which the machine is going to be free, after completing all tasks assigned to it.
Consider the example discussed above. Suppose the task list is given in the range
A19:B23. The range D19:J20, with number of rows = 2, and number of columns = 7, is highlighted and the function is invoked by typing in =lpt(2,A19:B23) followed by control+shift+enter. The function fills the range D19:J20 with the following output:

| D | E | F | G | H | I | J | 19 | 4 | 2 | 0 | 0 | 0 | 2 | 30 | 20 | 1 | 3 | 5 | 0 | 0 | 3 | 33 |

Write the VBA code for the function lpt as explained above.