Warning

This page is located in archive.

*Author: Radek Mařík*

*Edit: Tibor Strašrybka*

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

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

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

- Permutation scheduling and a single machine $1|d_j|\sum w_j \cdot T_j$
- 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.

- 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