Assignment 4: Planning and Scheduling

Assignment 4: Planning and Scheduling 8% of Final Mark 
1 Objectives
The goal of this assignment is to help you understand the basic concepts of planning and scheduling, and simple algorithms for them. In particular, the following topics should be reviewed: • Use Action Description Language (ADL) to represent a classical planning problem, • Use state-space search algorithms to find a plan, • Represent a schedule of job shop scheduling problem, • Generate a schedule by a dispatching rule for a given job shop scheduling problem, and • Find a solution for a vehicle routing problem using the nearest-neighbour heuristic. All the questions in this assignment can be answered without programming. You can simply write the answers to the questions in your report. These topics are (to be) covered in lectures 19–22. The online materials can also be checked.
2 Question Description
Part 1: Classical Planning – Monkey-and-Bananas [35 marks]
In this part, you are required to represent the monkey-and-bananas problem using ADL, and find a plan by forward (progression) state-space search.
Problem Description
In the monkey-and-bananas problem, a monkey, a box and some bananas are placed in a room. The bananas are hung from the ceiling and the monkey cannot reach them directly. The only way for the monkey to catch the bananas is to move the box under the bananas and climb up onto the box. Assume that initially, the monkey is at location A, box at location B and bananas at location C. The monkey and box have height Low, i.e. they are on the ground. The bananas have height High. If the monkey climbs onto the box, its height will be High. The monkey cannot catch the bananas when its height is Low. The actions that the monkey can take include (1) Go from one place to another, (2) Push the box from one place to another (assume the condition and the result of this action is that the box and the monkey are at the same current/new (precondition/effect) location), (3) ClimbUp onto or ClimbDown from the box (the monkey and box at the same location before/after climb-up/climbdown), and (4) Grasp and Ungrasp the bananas. The result of a Grasp is that the monkey holds the bananas, if the monkey and the bananas are in the same place at the same height. The goal state is that the monkey holds a banana.
Questions
1. (5 marks) Write the description for the initial and goal states using ADL.
2. (10 marks) Write all the action schemas in ADL representation (there are 6 actions in total). Each action should include a name, variables, precondition and effect. The precondition of each action should be set in a way that self-connection is avoided, i.e., no action connects any state to itself.
1
3. (15 marks) A plan to achieve the goal state from the initial state can be found by using forward state-space search. Based on the ADL in Questions 1 and 2, draw the first three layers of the corresponding state-space search graph to demonstrate the search process. • Each node (state) in the graph is represented by a conjunction of literals/predicates. • Each edge is associated with an action. • Each leaf node is either a goal state or a loop. Example: The figure below is the 5-layer forward state-space search graph of the vacuum cleaner’s world (the ∧ between predicates are omitted).
If you find it hard to draw the graph using drawing software, you can simply draw the graph by hand and scan it as an electronic copy.
4. (5 marks) Write a plan to achieve the goal state from the initial state. The plan needs to be formatted as follows: • Initial state: • Action 1: • State 1: • Action 2: • ... • State k (goal state):
2
Part 2: Job Shop Scheduling [40 marks]
In this part, you are required to find solutions (schedules) for a job shop scheduling problem.
Problem Description
The table below gives a job shop schedule problem with 3 jobs and 2 machines.
Job ArrivalTime Operation Machine ProcTime
J1 0
O11 M1 50 O12 M2 25
J2 10
O21 M2 30 O22 M1 35
J3 20
O31 M1 40 O32 M2 20
• (Number of operations) Each job Jj has two operations Oj1 and Oj2. • (Order constraint) The operations strictly follow the order constraint {Oj1 ≺ Oj2}. That is, Oj2 (j = 1,2,3) cannot be processed until Oj1 has been completely processed. • (Arrival time) Each job has an arrival time (ArrivalTime). For each job Jj, the first operation Oj1 cannot be processed earlier than its arrival time. • (Resource constraint) Each operation can only be process by a particular machine. For example, operation O11 can only be processed by machine M1. Each machine can process at most one operation at a time.
Solution/Schedule Representation
A solution/schedule for a job shop scheduling problem is a sequence of actions. Each action is composed of the processed operation, the machine to process the operation, and the starting time. The finishing time of an action is the starting time plus the processing time of the processed operation. The actions are sorted in the increasing order of starting time, i.e. the former action starts no later than the latter one. In this assignment, the following format is adopted to represent a schedule: Process(O11,M1,0) −→ Process(O21,M2,10) −→ ..., where Process(o,m,t) stands for an action that processes the operation o with machine m and starts at time t.
Questions 1. (10 marks) Given a schedule whose action sequence is as follows: Process(O11,M1,t1) → Process(O21,M2,t2) → Process(O31,M1,t3) → Process(O12,M2,t4) → Process(O22,M1,t5) → Process(O32,M2,t6). Since the sequence is sorted in the increasing order of starting time, we know that t1 ≤ t2 ≤ t3 ≤ t4 ≤ t5 ≤ t6. Calculate the earliest starting time (t1 to t6) of each action. You can draw gantt chart to help you think. Hint: the earliest starting time of an action is the later time between the earliest ready time of the operation and the earliest idle time of the machine.
2. (5 marks) For the solution given in Question 1, find the completion time of each job, which is the finishing time of its last operation. Then, calculate the makespan of the solution, which is defined as the maximum completion time of all the jobs.
3
3. (15 marks) Write the state from step 1 to step 3, and the final solution when applying the Shortest Processing time (SPT) dispatching rule to the problem. At each step, the representation of a state is composed of (1) a partial solution, (2) the earliest idle time of each machine and (3) the earliest ready time of each unprocessed operation. The initial state (step 0) is given below for your reference.
Step 0: • Partial solution: (empty, no action is scheduled) • earliestIdleTime(M1) = 0, earliestIdleTime(M2) = 0 • earliestReadyTime(O11) = 0, earliestReadyTime(O12) = ∞ • earliestReadyTime(O21) = 10, earliestReadyTime(O22) = ∞ • earliestReadyTime(O31) = 20, earliestReadyTime(O32) = ∞
4. (5 marks) For the solution obtained by the SPT rule, calculate the completion time of each job and the makespan. Compare the makespan between this solution with that obtained in Question 1 to find out which solution is better in makespan. Note: the solution in Question 1 is obtained by the First-Come-First-Serve (FCFS) rule.
5. (5 marks) The two compared solutions are obtained by the SPT and FCFS rules, respectively. If one solution is better than the other, does it mean that the rule that generates the better solution is better than the other rule? Why?
Part 3: Vehicle Routing [25 marks]
In this part, you are required to find a solution using the nearest neighbour heuristic and calculate its total cost for the given vehicle routing problem.
Problem Description
The graph below gives a vehicle routing problem.
● ● ● ●
●● ● ● ● ●
1 2
3
4
56
7
8
9
10
−1
0
1
2
3
−4 −2 0 2
Node x-coordination y-coordination Demand
1 (depot) 0 0 0 2 1 0 1 3 1 1 1 4 1 3 1 5 2 1 1 6 -1 1 1 7 -2 -1 1 8 0 2 1 9 -5 0 1 10 -5 2 1
The location and demand of each node is given as follows. Node 1 is the depot. Each node except the depot has a demand of 1. The capacity is 3. The cost of each edge is the Euclidean distance between the two end-nodes. The Euclidean distance matrix is given below.
4
D =
               
1 2 3 4 5 6 7 8 9 10 1 0 1.00 1.41 3.16 2.24 1.41 2.23 2.00 5.00 5.39 2 1.00 0 1.00 3.00 1.41 2.24 3.16 2.24 6.00 6.32 3 1.41 1.00 0 2.00 1.00 2.00 3.61 1.41 6.08 6.08 4 3.16 3.00 2.00 0 2.24 2.83 5.00 1.41 6.71 6.08 5 2.24 1.41 1.00 2.24 0 3.00 4.47 2.24 7.07 7.07 6 1.41 2.24 2.00 2.83 3.00 0 2.24 1.41 4.12 4.12 7 2.23 3.16 3.61 5.00 4.47 2.24 0 3.61 3.16 4.24 8 2.00 2.24 1.41 1.41 2.24 1.41 3.61 0 5.39 5.00 9 5.00 6.00 6.08 6.71 7.07 4.12 3.16 5.39 0 2.00 10 5.39 6.32 6.08 6.08 7.07 4.12 4.24 5.00 2.00 0 
              
Questions
1. (15 marks) Find a solution by the nearest neighbour heuristic. Write the solution as a set of node sequences starting and ending at the depot node (node 1). It should look like R1 = (1,...,1), R2 = (1,...,1), ....
2. (10 marks) Calculate the total length (Euclidean distance) for the obtained solution.
3 Notes
During the time between the assignment handout and submission, the tutor(s) will run a number of helpdesks to provide assistance.
4 Submission Guidelines
4.1 Submission Requirements
A document consisting of the answers of all the questions. The document can be written in PDF, text or the DOC format. You need to submit this document in both soft copy and hard copy.