Python code

In this assignment we are considering the maximum tardiness problem (Tmax) with ready times. The jobs have a ready time, processing time, and a due date. The Tmax value for a given sequence is found as follows: (i) calculate the tardiness values of all individual jobs, (ii) the highest tardiness value is the Tmax. The objective is to find the sequence with the minimum Tmax value. 1. Modify your previous code to implement the Tmax problem with ready times. Run your code for increasing number of jobs and make sure that you find the optimal solution. 2. Implement the Branch and Bound (B&B) algorithm discussed in class. The B&B algorithm is based on doing the following during the search for the optimal solution: 1. Keeping an Upper Bound (UB) for minimum Tmax value. Whenever you find a complete sequence and compute its Tmax value, update the upper bound. An upper bound is the best Tmax value you found so far. 2. Calculating a Lower Bound (LB) for every partial sequence. When you pop a node from the stack and figure that it is a partial sequence, you should calculate a LB value associated with that partial sequence. If the LB > UB, then you discard that node and pop the next one from stack. Otherwise, you expand the node and push resulting new nodes to the stack. This helps to prune non-promising parts of your search tree and reduces computation time. 3. Run your code in (1) and (2) on the same data set and verify that the optimal solution found by complete enumeration is the same as the one found by B&B algorithm. Run both code for an increasing number of jobs and, show and compare their computation times. Remember how we described a lower bounding function for the Tmax problem with ready times. At any node in the search tree, except the terminal nodes, you have a partial sequence. Consider a partial sequence: there are fixed jobs and free jobs. Now consider the free jobs and order them in increasing due dates, which will give you a sequence for the free jobs. Append the sequence for the free jobs to the fixed sequence and you have a sequence for the full set of jobs. The next step is to create the schedule and compute the tardiness of each job. For the first part of the sequence, which is made up of the fixed jobs, consider the ready times and calculate the jobs' tardiness. For the second part of the sequence, which is made up of the free jobs, ignore the ready times assuming they are immediately available for processing, and calculate the jobs' tardiness values. Then identify the Tmax value, which corresponds to the Lower Bound. CODE from random import seed, randint proc, due = 'proc', 'due' n = 4 seed(2) def create_instance(n): jobs = [] for j in range(n): job = {} job[proc] = randint(1,10) job[due] = randint(10,20) [login to view URL](job) return jobs jobset = create_instance(n) stack = [] root = [] [login to view URL](root) alljobs = range(n) while len(stack) > 0: node = [login to view URL]() if len(node) == n: print "Full solution", node else: free = [i for i in alljobs if i not in node] for j in free: newnode = list(node) [login to view URL](j) [login to view URL](newnode)