Warning
This page is located in archive.

Permutation scheduling

Author: Radek Mařík
Edit: Tibor Strašrybka

The following files are to be included in a single zip archive:

  1. Source code solving the scheduling problem. Use an appropriate programming language or a computational environment.
  2. Input data file, see the following description.
  3. A file including results according to following guidelines:
    1. A list with the starting schedule.
    2. A list with durations of all tasks $p_j$.
    3. A list with deadlines $d_j$.
    4. A list with weights of each task task $w_j$.
    5. Find the best schedule and its price for each step.
    6. The best schedule, including its price.

All tasks are based on the following specification of a scheduling problem:

  1. Permutation scheduling and a single machine $1|d_j|\sum w_j \cdot T_j$
  2. Find the optimal schedule using tabu search.

We suggest that you create a smaller instance of the problem and use it verify that your program behaves correctly.

Scheduling problem assignment

  • Optimization criterion: minimize the accumulated non-negative delay.
  • Schedule neighborhood: All schedules acquired by a pair-wise swap of neighboring tasks.
  • Schedule selection from neighborhood: Finds the best schedule for each step from the neighborhood.
  • Tabu list: pairs of tasks, swapped in last 11 modifications.
  • There are 15 tasks with names from „1“ to „15“.
  • The initial schedule is [2, 3, 15, 6, 5, 10, 8, 7, 13, 14, 1, 4, 12, 9, 11].
  • Task lengths are (4, 16, 6, 5, 9, 19, 1, 13, 12, 20, 20, 19, 5, 18, 12).
  • Deadlines are (36, 67, 105, 53, 77, 124, 194, 157, 25, 202, 43, 61, 5, 7, 8).
  • Weights are (21, 45, 35, 73, 1, 28, 21, 14, 76, 70, 51, 23, 69, 62, 80).
  • Perform 200 iterations.

courses/ae3b33kui/seminars_and_labs/12.txt · Last modified: 2016/02/14 22:47 by xnovakd1