Home Page > > Details

COMP307/AIML420 — Introduction to AI

Assignment 4: Planning and Scheduling

8% of Final Mark — Due: 23:59 Wednesday 1 June 2022

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:

• Represent a schedule of job shop scheduling problem,

• Generate a schedule by a dispatching rule for a given job shop scheduling problem,

• Solve vehicle routing problem using heuristics.

This assignment is largely writing report, and you will need to write the program for solving the vehicle routing

problem in Part 3.

Part 1: 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. 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:

P rocess(O11, M1, 0) → P rocess(O21, M2, 10) → . . . ,

where P rocess(o, m, t) stands for an action that processes the operation o with machine m and starts at time t.

1

Questions

1. (10 marks) Given a schedule whose action sequence is as follows: P rocess(O11, M1, t1) → P rocess(O21, M2, t2) →

P rocess(O31, M1, t3) → P rocess(O12, M2, t4) → P rocess(O22, M1, t5) → P rocess(O32, M2, t6). Since the sequence is sorted in the non-decreasing 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 a 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. (10 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. (10 marks) Write the final solution obtained by the Shortest Processing time (SPT) dispatching rule.

You may draw a figure (gantt chart) to help you find the solution.

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 terms of 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 then the other, does it mean that the rule that generates the better solution is better than the other

rule? Why or why not?

6. (for AIML420 ONLY, 10 marks) Often in practice, neither the SPT nor FCFS rules are good enough for

solving the job shop scheduling problem. Suggest two methods to solve the job shop scheduling problem. One

method should consider the problem to be static (all information is known in advance), and the other method

should consider it to be dynamic (e.g. unpredicted job arrivals can happen in real time). Clearly describe

your methods (e.g. algorithm framework, solution representation/encoding, search operators).

2

Part 2: Vehicle Routing [60 marks]

Every day, a delivery company needs to deliver goods to many different customers. The deliveries are achieved by

dispatching a fleet of vehicles from a centralised storage warehouse. The goal of this problem is to design a route for

each vehicle so that all of the customers are served by exactly one vehicle and the travel distance of the vehicles is

minimised. Additional problem complexity comes from the fact that the vehicles have a fixed storage capacity and

the customers have different demands.

Below is an example of the Vehicle Routing Problem (VRP). The red box indicates the central warehouse (depot),

and each circle is a customer distributed in the 2D space. There are 6 vehicles routes, each with a different colour.

Each route starts from the depot, serves a subset of customers, and returns to the depot again. Each route satisfies

the capacity constraint, i.e. the total demand of the customers served by the route does not exceed its capacity.

Data

In the provided vrp-data.zip, there are two VRP instances, along with their corresponding optimal solutions. The

instance is named with n(n)-k(k).vrp, where n is the number of customers and k is the number of vehicles. The

corresponding solution is named as .sol.

The instance file is basically self-explained.

• It starts with some information rows including “NAME”, “COMMENT”, “TYPE”, “DIMENSION”,

“EDGE WEIGHT TYPE”, which you can ignore/skip safely.

• The row “CAPACITY” gives the capacity of the vehicles.

• Under “NODE COORD SECTION”, each row shows the coordinates of each node (customer), in the format

of “index x-coordinate y-coordinate”.

• Under “DEMAND SECTION”, each row shows the demand of each node, in the format of “index demand”.

• Under “DEPOT SECTION”, the first row is the index of the depot, and the second is −1, indicating the end

of the file.

3

To help you code, you are provided two template codes, one in Python and the other in Java. You can use either

of them to work on this part. Of course, you can also write your own code from scratch if you like.

Python Template Code

In the provided python.zip, there are three Python template code file to help you load the .vrp instance file, read

a .sol solution file, and visualise a solution.

• The loader.py file contains the following functions:

– load data(): read a VRP instance from a .vrp file.

– load solution(): read a VRP solution from a .sol file.

• The utility.py file contains the following functions:

– calculate euclidean distance(): calculate the Euclidean distances between two nodes. This is a

TODO item if you use this template code to do the assignment.

– calculate total distance(): calculate the total Euclidean distance of a solution. This is a TODO

item if you use this template code to do the assignment.

– visualise solution(): visualise the solution on a 2D figure.

• The main.py file contains the following functions:

– main(): the main function with three examples that read the .vrp file, and then (1) read its optimal

solution from the .sol file, and visualise the optimal solution; (2) construct a solution using the nearest

neighbour heuristic and visualise it; (3) construct a solution using the savings heuristic and visualise it.

– nearest neighbour heuristic(): construct a solution using the nearest neighbour heuristic. This is a

TODO item if you use this template code to do the assignment.

– savings heuristic(): construct a solution using the savings heuristic. This is a TODO item if you use

this template code to do the assignment.

The template code relies on the numpy and matplotlib Python libraries. You should install these libraries if you

haven’t.

• Installing numpy: https://numpy.org/install/.

• Installing matplotlib: https://matplotlib.org/stable/users/installing.html

Java Template Code

In the provided java.zip, there are the following .java template Java files.

• The VRPInstance.java file is the data structure for a VRP instance.

• The VRPSolution.java file is the data structure for a VRP solution.

• The VRPNode.java file is the data structure for a node.

• The VRPIO.java file is the I/O file containing the following functions:

– loadInstance(): read a VRP instance from a .vrp file.

– loadSolution(): read a VRP solution from a .sol file.

– writeSolution(): write a VRP solution into a .sol file.

• The main.java file contains a main() function. It reads a .vrp instance file. Then, it generates a nnSol

solution by the nearest neighbour heuristic, a svSol solution by the savings heuristic. Finally, it writes the

nnSol into the nn.sol file, and svSol into the sv.sol file.

4

– NB: You can use the main.py Python file to read the obtained .sol solution files and visualise

them.

• The Utility.java file contains the following functions:

– calculateEuclideanDistance(): calculate the Euclidean distances between two nodes. This is a TODO

item if you use this template code to do the assignment.

– calculateTotalCost(): calculate the total cost (Euclidean distance) of a solution. This is a TODO

item if you use this template code to do the assignment.

– nearestNeighbourHeuristic(): construct a solution using the nearest neighbour heuristic. This is a

TODO item if you use this template code to do the assignment.

– savingsHeuristic(): construct a solution using the savings heuristic. This is a TODO item if you use

this template code to do the assignment.

Implementation

• A straightforward way is to fill in the following TODO items in the template code.

– For the Python template code, they are in

∗ The main(), nearest neighbour heuristic() and savings heuristic() functions in main.py.

∗ The calculate euclidean distance() and calculate total distance() functions in utility.py.

– For the Java template code, they are in the Utility.java file.

∗ After obtaining the .sol files, complete the main() function in main.py to read the .vrp file and the

.sol files generated by your code, and visualise them.

∗ This can simply be done by calling the loader.load solution() and utility.visualise solution()

functions.

• If you do not want to use the template code, you can

– use any other language to (1) read the .vrp file, (2) generate the solution using the required heuristics,

and (3) output the solution in the same format as in the given .sol files.

– complete the main() function in main.py to read the .vrp file and the .sol files generated by your code,

and visualise them.

– write a clear readme file to run your source code on an ECS Desktop to generate the .sol files.

Requirement

1. (20 marks) Implement the nearest neighbour heuristic to generate a VRP solution. The distance between two

nodes is defined as the Euclidean distance. That is, given two nodes v1 = (x1, y1) and v2 = (x2, y2), the

distance is calculated as

dist(v1, v2) = p (x1 − x2)

2 + (y1 − y2)

2

2. (20 marks) Implement the savings heuristic to generate another VRP solution.

3. (20 marks) In the report, use the Python template code to visualise the solutions obtained by the heuristics,

compare the solutions generated by the two heuristics and the optimal solution and discuss the differences

between their performance.

4. (for AIML420 ONLY, 10 marks), Suggest a more advanced method that can be better than the above

two heuristics. Clearly describe your methods (e.g. algorithm framework, solution representation/encoding, search operators).

5

2 Notes

During the time between the assignment handout and submission, the tutor(s) will run a number of helpdesks to

provide assistance.

3 Submission Guidelines

3.1 Submission Requirements

1. Programs (Executive program file and source files) for Part 2. Please provide a readme file that specifies

how to compile and run your program. A script file called sampleoutput.txt should also be provided to show

how your program run properly. If you programs cannot run properly, you should provide a buglist file.

2. A report document that consist of the answers of all the individual parts. The document should mark

each part clearly. The document can be written in PDF, text or the DOC format.

3.2 Submission Method

The programs and the PDF report should be submitted through the web submission system (accessible from the

COMP307 or AIML420 course web site) by the due time. Please ensure you submit to the correct system based

on which course you are enrolled in!

3.3 Late Penalties

The assignment must be submitted on time unless you have made a prior arrangement with the course coordinator

or have a valid medical excuse (for minor illnesses it is sufficient to discuss this with the course co-ordinator.)

The penalty for assignments that are handed in late without prior arrangement is one grade reduction per day.

Assignments that are more than one week late will not be marked.

Remember that you have three late days for this course (which can be used fractionally), but that these apply

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Help With Ece 380,Help With Java/Pytho... 2023-02-23
- Help With Econ5102,Python/Java Program... 2023-02-23
- Cisc 360Help With ,C/C++ Programminghe... 2023-02-23
- Help With Stat 411,Help With Java/Pyth... 2023-02-22
- Comp90048help With ,Help With Java，C/... 2023-02-22
- Help With Ma1510,Help With C++/Java Pr... 2023-02-21
- Csci561 Programminghelp With ,Help Wit... 2023-02-21
- Econ 178Help With ,Help With R Program... 2023-02-20
- Help With Ecmm461,C/C++ Programminghel... 2023-02-20
- Msmk7021help With ,C++，Python Program... 2023-02-20
- Comp5400help With ,Help With Java/Pyth... 2023-02-20
- Cse214help With ,Help With C/C++，Java... 2023-02-20
- Help With Math5965,Help With R Program... 2023-02-20
- Help With Comp9012,Help With Python Pr... 2023-01-23
- Comp9414: Artificial Intelligence Assi... 2023-01-05
- Comp9444 Assignment 1 Neural Networks ... 2023-01-05
- Final Assignment - Apply All Your Skil... 2023-01-05
- Data7202 Statistical Methods For Data ... 2023-01-04
- Comp307/Aiml420 Assignment 4: Planning... 2023-01-04
- Comp3170 Assignment 3 Moonlit Forest 2023-01-04

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！