Reference no: EM132324530
Project Scheduling -
The following problem is inspired by the situation encountered in a truck cross-docking platform. Some boxes arrive in the platform in a random order, where they are grouped by destination into carts, before to be loaded into the shipping trucks. Some robots as well as manual workers are available to place the boxes in the carts. The manager of the cross-docking platform wants an algorithm to assign the boxes processed by the robots. The main objective is to maximize the workload of the robot.
To model this situation as a scheduling problem, only the robot will be considered. A job consists in picking a box and placing it in the cart. Each job j has a release date rj (the arrival date of the box in the picking zone) and a color cj (the destination of the box). Due to limited storage, a box cannot stay too much time in the shop. Therefore, each job must either be processed by a machine before its deadline d-j , or it can be rejected. If the job is rejected, the associated box is moved to the manual loading area (thus it is not considered in the robot's schedule). The goal is to maximise the amount of work performed by the robot. In other words, the objective is to minimize the number of rejected jobs.
The policy of the platform is to assign full carts only to the robots. Therefore, batches of exactly b jobs of the same color must be created to process by the robots. The processing time of a batch is fixed to p time units.
|
Job j
|
rj
|
d-j
|
cj
|
|
1
|
1
|
7
|
1
|
|
2
|
4
|
14
|
2
|
|
3
|
5
|
15
|
2
|
|
4
|
10
|
15
|
1
|
|
5
|
11
|
16
|
1
|
|
6
|
12
|
17
|
1
|
|
7
|
12
|
17
|
1
|
|
8
|
12
|
17
|
2
|
|
9
|
12
|
17
|
2
|
|
10
|
12
|
17
|
2
|
|
11
|
12
|
17
|
2
|
|
12
|
12
|
17
|
2
|
|
Table 1: Small instance of the considered problem
|
A small example is given in Table 1, with a single robot, b = 2, and p = 2. The solution for this instance is to schedule the batches {2, 3}, {4, 5}, {6, 7}, {8, 9} ({I, j} denotes a batch with job i and j), and Figure 1 gives the associated Gantt chart.
In this project, you have to propose and implement an algorithm to solve this problem. The files 'Data10min.csv', 'Data1hour.csv', 'Data1Day.csv' give input of different sizes. In the Java archive 'Scheduling2019.zip', a class has been implemented to read the instances. The output of your algorithm must indicated the set of rejected jobs, as well as for each batch:
- The set of jobs in the batch.
- The machine that processes the batch.
- The starting time and completion time of the batch.
Attachment:- Assignment Files.rar