Task Scheduling Heuristics

Scheduling problems arise when it is necessary to define the sequence of task execution in order to minimize costs or losses resulting from delays or advancements in the end of execution in relation to the established deadline.

This approach can be used in various areas, such as Project Management, Production Planning, Machinery Allocation and Logistics. The scheduling problem can be modeled with 4 parameters for each task:

• dj Task j's deadline
• pj Task j's processing time
• hj Task j's penalty for advancement
• wj Task j's penalty for delay

The solution consists of determining the execution sequence that generates the lowest possible penalty, considering that all tasks will be executed sequentially without parallelism. These problems are classified as NP-hard, therefore, ILP (Integer Linear Programming) models only apply to problems with few tasks. For larger dimension problems, heuristic methods are often used.

In this project, the following heuristics were implemented:

• SPT (Shortest Processing Time): Process tasks with the shortest processing time first p1 ≤ p2 ≤ ... ≤ pn.

• LPT (Longest Processing Time): Process tasks with the longest processing time first p1 ≥ p2 ≥ ... ≥ pn.

• WSPT (Weighted Shortest Processing Time): Process tasks with the smallest ratio between the fine for delay and the processing time first (w1/p1) ≥ (w2/p2) ≥ ... ≥ (wn/pn).

• WLPT (Weighted Longest Processing Time): Process tasks with the smallest ratio between the fine for advancement and the processing time first (h1/p1) ≤ (h2/p2) ≤ ... ≤ (hn/pn).

• EDD (Erliest Due Date): Process tasks with the earliest deadline first d1 ≤ d2 ≤ ... ≤ dn.

• MST (Minimum Slack Time): Process tasks with the smallest difference between the deadline and the processing time first
  (d1–p1) ≤ (d2–p2) ≤ ... ≤ (dn–pn).

The performance of each heuristic may vary according to the characteristics of the set of tasks.

Usage

Windows

In windows, the program can be run in two ways:

• Run the self-contained SchedulingHeuristics.exe to open the interface (may take a few seconds).

or

• Open a command prompt CMD in the folder containing "SchedulingHeuristics.py" and run:

pip install -r requirements.txt

py SchedulingHeuristics.py

OBS: In this case, Python and pip are required. Virtual environment is recommended.

Linux

• Open a terminal in the folder containing "SchedulingHeuristics.py" and run:

pip install -r requirements.txt

py SchedulingHeuristics.py

OBS: In this case, Python and pip are required. Virtual environment is recommended.

---

OBS:

• The spreadsheet containing the task data must be provided in the same folder that the program;
• The spreadsheet must be closed when click in "Start";
• After "Calculations Completed" message, the spreadsheet can be opened and the results will be updated;
• The number and name of tasks can be modified;
• The fine and time units must match. Ex: Deadline in days, fine per day. Deadline in hours, fine per hour.

Expected result:

Support

If you want some help with this work contact me: [email protected]