MIE562-Assignment 1 Solved

You can find definitions of the job shop scheduling problem and the SPT dispatch rule in the course slides and/or textbook. In this section, we provide details on how we represent the problem instances and the conventions used.

1.1         Instance Files
Each instance file consists of the following:

•    a line of description

•    a line containing the number of jobs and the number of machines

•    then one line for each job, listing the machine number and processing time for each step of the job.

The machines are implicitly numbered starting at 0. Here is an example instance file.

Sample Instance

2 3

2 1 0 3 1 6

0 8 1 5 2 10

In this instance there are 2 jobs and 3 machines. Job 0 is on line 3 and job 1 line 4. Job 0, operation 0 requires machine 2 and has a processing time of 1. Job 0, operation 1 requires machine 0 and has a processing time of 3. And so on.

This format follows the standard JSP instance format (see http://people.brunel.ac.uk/ ~mastjjb/jeb/orlib/files/jobshop1.txt) and so you should be able to find many test problems for your code.

A small set of instances, with answers, has been posted for you on Quercus (see Coding Assignment #1). You are strongly encouraged to create (or find) your own instances to test your code.

1.2         Job Numbering
Jobs are numbered starting at zero. Each job row in the instance corresponds to a job with the numbering starting at zero and incrementing by 1 with each line (e.g., the row after Job 0 contains Job 1). Operations within each job are numbered starting at zero; again they increment by one. As such, an operation can be uniquely identified by the pair of its job number and operation number within its job. So the first operation in Job 0 is (0,0), the second operation is (0,1), and so on.

1.3         Tie Breaking
It is important that you follow this tie breaking rule to ensure that your algorithm finds the same solutions as the one we have implemented and will compare against.

In your algorithm, you must use the SPT dispatch rule to order the list of available operations on each machine. Depending on the data, you may have to order two or more operations with the same processing time. If this happens, you are guaranteed that each operation will come from a different job.[1] Therefore, to break ties, you should order the operations in ascending order of job number.

For example, if you have operation (3,2) (i.e., job 3, operation 2) and operation (4,0) both with processing time 10 and both available to be executed on the same machine, then (3,2) should come before (4,0) in your list because 3 < 4.

2           Coding and Marking Details
We will use the automated marking system called MarkUS to mark your code (see “Marking Scheme” below). MarkUS is running Python 3.8.3 and your code needs to work with this version of Python.[2]

In this section, we provide the coding requirements and other necessary information for using the MarkUS grading system.

2.1         Function Definition
You must submit a Python file called coding1.py that contains (perhaps among other functions) a function with the following signature:

run SPT(instance), where instance is a string of the filename of the instance (e.g.,

“ft06.txt”).

The function should read in the problem instance (assume it is in the same folder as the coding1.py file) and solve the problem with the SPT dispatch rule with tie breaking as described above.

The function should return a tuple containing:

•    the makespan: integer

•    a schedule: a dictionary with keys corresponding to the job number and values being a list of start times for that job’s operations following that job’s operation order.

For example the solution to the “Sample Instance” given above is:

(23, {0: [0, 8, 13], 1: [0, 8, 13]})

The makespan is 23. Job 0, operation 0 starts at time 0. Job 0, operation 1 starts at time 8. Etc.

MarkUS will call your function and parse the return value to compare it against the correct answer. It is important that you follow the above instructions exactly.

Do not put any input or print statements in your code.


 
[1] I will leave it to you to figure out why this is true.
[2] Generally, as long as you are using Python 3.5 or greater, you should not have a problem.