Summary
This assignment involves work as an individual to write code to implement one of four greedy
strategies for solving a job scheduling problem, and also as a group to write a group report that
evaluates the effectiveness of the strategies. The assignment should be done in groups of 3 or 4, with
each group member implementing a different strategy. It is strongly recommended that you form. a
group with other students from your lab session, so you have chances to work together often. For the
components of the mark that are based on the group report, all members of the group get the same
score. For the programming, each student gets a score based on the code they wrote and submitted as
an individual.
It could be helpful to study the lecture (week 11) and read the chapter on Greedy Algorithms in
Algorithm Design and Applications by Goodrich and Tamassia, before attempting the assignment. In
particular, slide 16 of the lecture indicates how you can evaluate different greedy strategies.
Submission details
• Due: Friday June 8 (Week 13) at 11pm
• Submit your report via Canvas through Turnitin. You may resubmit as often as you wish
without penalty, until the due date. (We will mark whichever submission is the latest among
those before the due date.)
• Submit your report as a single document (preferably a pdf or doc file). Your work must be
typed text. (No images of text, although you can use diagrams if you think it helps.)
• To support anonymous marking, do not put the names of any members of your group on the
document, nor include your names in the filename. (It is fine to put SID on the document or
the filename.)
• Submit your source code in the Assessments section on Ed. You should only submit your
own code (not that of other members of your group). You may resubmit as often as you wish
without penalty, until the due date. (We will mark whichever submission is the latest among
those before the due date.)
• Value: 10% of the unit
• Language: You may choose to program in either Python or Java.
• Your code should be your own (except where you include scaffold code that we have provided,
or code that is acknowledged to come from textbooks or other sources). Your report should be
the work only of the group members. Make sure that you acknowledge sources of information,
and any direct quotations. We will be using similarity matching software on your code and
on your report. Please do not plagiarize; make sure that you follow the University policy
on academic honesty.
Group formation
Each group should consist of either 4 members, or 3 members. All members should be enrolled
in the same unit (e.g. do not mix comp2823 with comp2123, or comp9123 with comp2123 in a
single group). We recommend that all members be attending the same lab session, but that is not
a requirement. The tutors have authority to rearrange groups if necessary, to ensure all groups are
appropriate size.
If there are difficulties in managing the work of the group, or agreeing on how to write the report, etc,
you should contact the unit coordinator as soon a possible, to leave enough time to resolve the issues.
1 Task Description
1.1 Scenario
Consider the following scheduling problem. You have a set J = fJ1;J2;:::;Jng of n job offers.
Each job Ji, 1 i n, starts at time si and finishes at time fi. Each job pays the same amount,
irrespective of duration; for simplicity, we’ll assume that each job that you finish pays $1. Two jobs
are said to be compatible if they do not overlap in time (you can only perform. one job at a time). The
problem is to make as much money as possible given the sets of jobs in J, that is, find the maximum
subset of mutually compatible jobs in J.
s1 = 3, f1 = 6 J1
s2 = 6, f2 = 10 J2
s3 = 1, f3 = 4 J3
s4 = 5, f4 = 7 J4
s5 = 0, f5 = 3 J5 Time
0 2 84 106
Figure 1: An input instance for the scheduling problem. The optimal solution is $3 withfJ1;J2;J5g.
Data Structures and Algorithms Page 2 of 6
COMP2123/2823/9123
An example is shown in Fig. 1 where the input consists of five jobs J =fJ1;:::;J5g. Note that job
intervals are displayed at different elevations to assist visualization only.
1.2 Strategies
Your task is to investigate the following four greedy strategies and determine which one performs the
best. In each case, ties are broken arbitrarily.
Shortest interval: Consider jobs in ascending (increasing) order of interval length fi si.
Earliest finish time: Consider jobs in ascending order of finish time fi.
Fewest conflicts: For each job, count the number of conflicting jobs ci. Schedule in ascending order
of conflicts ci.
Earliest start time: Consider jobs in ascending order of start time si.
In each strategy, jobs are sorted according to the specified order, and then each job, considered from
first to last in the ordering, is included in the output if it does not conflict with previously included
jobs, and excluded otherwise.
1.3 Requirements
Each member of your group must implement one of the four greedy strategies given above (different
members implement different strategies). If there are only three members in your group, implement
the first three strategies among the members.
Your tasks as a group are to:
• Develop a set of experimental instances that you will run your implementations on, for
evaluating the strategies. Try to develop instances where some of the strategies perform
poorly. In particular, you should try to include instances which make each of the strategies
return results which are as far from the optimal solutions as possible.
• Write a report consisting of the following:
– A discussion of the way you evaluate the strategies; in particular you need to describe the
instances you used in the experiments (and why you chose these particular ones), and you
should explain how you summarised the results from the different instances.
– A presentation of the results of your experiments. Your presentation should include, for
each strategy that your group implemented, an account of the quality of the solutions
found by that strategy. You should include explicit mention of the worst case you found
(that is, which instance gave the worst ratio between the score provided by the solution of
the strategy you are considering, and the best score you know for that instance)
Data Structures and Algorithms Page 3 of 6
COMP2123/2823/9123
2 Implementation (Individual work)
2.1 Scaffold
You may implement your submission in either Java or Python (and it is fine if different students in
the group choose different languages). The only file which you need to edit is JobScheduling.java
or job_scheduling.py, which contains four empty methods – one for each strategy. You only need to
implement one of these, according to which greedy strategy you are implementing for your group.
There is also a Job class defined in a separate file, which you should not modify. Each Job object
consists of an id (integer), a startTime (float), and a finishTime (float).
The JobScheduling.java and job_scheduling.py files also include a main method which you can use
for your own purposes, a loadJobs method which you can use to load job scheduling instances in
from standard input or from a file, and a number of commented-out declarations of a variable named
chosen.
To indicate which strategy you have chosen to implement for your group, uncomment the definition of
the chosen variable which corresponds to your choice. If you do not do this, your code submission
may not be marked.
You are allowed to write additional methods, classes, etc., and add additional source files to your
assignment workspace as you see fit, though take note of the plagiarism notice above.
2.2 Libraries
You may, and indeed are expected to make use of data structures either built into your language of
choice or supplied by your language’s standard library. You may make use of other features of your
language of choice’s standard library, and any code provided in the textbooks for this course.
Use of external libraries is not allowed.
2.3 Job Scheduling Instances From Text Input
If you use the loadJobs method, you need to specify jobs to load in a specific format. loadJobs
expects each job to appear on a new line, and to be given by its fields, separated by spaces, in the
following order: id, startTime, finishTime.
For example, job scheduling instance given in Fig. 1 can be provided by the following input:
1 1 3 6
2 2 6 10
3 3 1 4
4 4 5 7
5 5 0 3
Data Structures and Algorithms Page 4 of 6
COMP2123/2823/9123
3 Report (Group work)
You must write a report, and submit it via Turnitin. The report should have a heading which gives the
SIDs of all members (but not your names!) and also indicates which unit you are all enrolled in.
The report contains the following content:
• A section that describes how the evaluation was done, including the details of the instances on
which each strategy was run.
• A section that presents the results of the evaluation, for each of the strategies your group imple-
mented. You are encouraged to use tables or charts to convey this information clearly.
• If the group consists of postgraduate students enrolled in COMP9123, there needs to be an
extra section, in which you suppose that you work for a company that needs to allocate tasks
to a specialist employee. They want to use this employee for as many jobs as possible, but
the employee can only work on one job at a time. Currently the company uses an exhaustive
search program to find the optimal solution to this problem, but a proposal has been made to
change to a different algorithm in order to run the allocation decision-making faster. Make a
recommendation to the management about this proposal.
4 Grading scheme
Individual code, Automatic grading [4 points for COMP2123/2823, 2 points for COMP9123].
The Ed platform. will check whether the program produces the appropriate output on various inputs.
Some of the inputs we check will be visible to you during submission (these are called public tests).
There are other inputs which we check only after the due date. Your grade in this aspect depends on
the number of our inputs where your implementation generates the appropriate allocation.
Group report, description of experiments [2 points]. This is based on the corresponding section of
your report. To gain a pass, your report will contain a clear description which gives enough details of
the instances checked and of the way the results are used, so the reader could reproduce the results. A
distinction will need a diverse set of instances, along with clear reasons why each is included in the
experiments. For full marks here, your instances must meet the distinction criteria and also they need
to include those that stress each strategy as much as possible.
Group report, description of results [4 points]. This is based on the corresponding section of
your report. To gain a pass, your report will contain a clear and easy-to-read description, for each
of the strategies your group implemented, of what you learned about the ratio between the score of
the solution found by that strategy and the best score found on that instance by any strategy. For a
distinction, your report will need to explain the features of the instance that lead to especially low or
high values for that ratio, and it will also need to have found values for the ratio that are nearly as
extreme as possible. Just as an example, if there is a strategy where some instances exist where the
ratio is 0.1, and the lowest ratio you report is 0.6, then do not expect a distinction score here! For full
marks, you need to get the distinction aspects and in addition, you must identify the true optimum for
each input instance used, and report on how the score obtained by the strategy relates to that. (You
must be able to argue that you have found the true optimum, not just state what it is).
Data Structures and Algorithms Page 5 of 6
COMP2123/2823/9123
Recommendation for replacing exhaustive search [2 points], only for a group of students from
COMP9123. This is based on your report. To gain half these points, this part of your report must
be clear and well-structured, written appropriately for the setting, and making sensible observations
(in particular, it needs to identify both positive and negative consequences from the proposal). Three-
quarters of the marks would indicate a report where your arguments really help the managers make
the decision, by distinguishing the conditions under which a change is appropriate, and those where
it isn’t. Full marks are for an exemplary answer.