1 Introduction
1.1 System characteristics
1.2 Related research
1.3 Contributions and outline of the paper
2 System model
2.1 Periodic task system
Entity | Parameter | Notation |
---|---|---|
System | Duration of a major frame |
P
|
CMs |
\(\mathcal {H}^{\text{CM}}\)
| |
AMs |
\(\mathcal {H}^{\text{AM}}\)
| |
Tasks |
\(\mathcal {I}\)
| |
Dependencies |
\(\mathcal {D}\)
| |
Chains |
\(\mathcal {C}\)
| |
AM h | Tasks |
\(\mathcal {I}_{h}\)
|
Idle time between task i and task j |
\(l^{\text{idle}}_{ij}\)
| |
CM h | Tasks |
\(\mathcal {I}_{h}\)
|
Task i | Execution requirement |
\(e_{i}\)
|
Period |
\(p_{i}\)
| |
Release time |
\(t_{i}^{\text{r}}\)
| |
Deadline |
\(t_{i}^{\text{d}}\)
|
2.2 Precedence relations
Entity | Parameter | Notation |
---|---|---|
Dependency d | Minimum length |
\(l_{d}^{\text{min-dep}}\)
|
Maximum length |
\(l_{d}^{\text{max-dep}}\)
| |
From task and job |
\(i_{d}, k_{d}\)
| |
To task and job |
\(j_{d}, l_{d}\)
| |
Chain c | Dependencies |
\(\mathcal {D}^{\text{chain}}_{c}\)
|
2.3 Communication network
Entity | Parameter | Notation |
---|---|---|
CN | CN-messages |
\(\mathcal {M}\)
|
CN-slots |
\(\mathcal {N}\)
| |
CM | CN-messages that are received on CM h |
\(\mathcal {M}^{\text{recv}}_{h}\)
|
CN-messages that are sent on CM h |
\(\mathcal {M}^{\text{send}}_{h}\)
| |
CN-message m | Required capacity |
\(l^{\text{msg}}_{m}\)
|
Tasks |
\(\mathcal {I}^{\text{msg}}_{m}\)
| |
CN-slot n | Capacity |
\(l^{\text{slot}}_{n}\)
|
Task i | Release time in CN-slot n |
\(t^{\text{r}}_{in}\)
|
Deadline in CN-slot n |
\(t^{\text{d}}_{in}\)
|
3 Sequencing approach
3.1 Strategy
-
Create a section for each part of a major frame that is not occupied by a fixed task and require that each non-fixed task is assigned to a section.
-
Create a subset for each set of non-fixed tasks that can be assigned to the same section and require that there is no overlap between tasks in this subset.
3.2 Notation
Entity | Parameter | Notation |
---|---|---|
CM h | Sections on CM h |
\(\mathcal {R}_{h}\)
|
Subsets on CM h |
\(\mathcal {S}_{h}\)
| |
Section r | Duration |
\(l^{\text{sec}}_{r}\)
|
Tasks |
\(\mathcal {I}^{\text{sec}}_{r}\)
| |
Subset s | Tasks |
\(\mathcal {I}^{\text{sub}}_{s}\)
|
Task i | Release time in section r |
\(t^{\text{r}}_{ir}\)
|
Deadline in section r |
\(t^{\text{d}}_{ir}\)
| |
Sections |
\(\mathcal {R}^{\text{task}}_{i}\)
|
3.3 Validity of the strategy for sequencing
-
Case \(i \in \mathcal {I}^{\text{fix}}_{h}\), \(j \in \mathcal {I}^{\text{fix}}_{h}\): It follows from the feasibility of the instance that i and j cannot overlap.
-
Case \(i \in \mathcal {I}^{\text{fix}}_{h}\), \(j \in \mathcal {I}^{\text{}}_{h}{\setminus }\mathcal {I}^{\text{fix}}_{h}\): There is no overlap between task i and task j since task j is assigned to a section by Constraints (4.1.6)–(4.1.8) and task i can, according to the definition of a section, not be scheduled in a section.
-
Case \(i \in \mathcal {I}^{\text{}}_{h}{\setminus }\mathcal {I}^{\text{fix}}_{h}\), \(j \in \mathcal {I}^{\text{}}_{h}{\setminus }\mathcal {I}^{\text{fix}}_{h}\): If task i and task j are assigned to different sections, they do not overlap since the sections are disjoint. If task i and task j are assigned to the same section, there exists a subset s, \(s \in \mathcal {S}_{h}\), such that \(\mathcal {I}^{\text{sub}}_{s}\) contains task i and task j and they are thereby ensured not to overlap by Constraints (4.1.11)–(4.1.14). \(\square \)
4 Mixed-integer programming formulation
4.1 Tasks and sequencing
4.1.1 AM-scheduling
4.1.2 CM-scheduling
4.2 Precedence relations
4.3 CN-scheduling
5 Solution approach
5.1 Constraint generation procedure
5.1.1 Relaxed problem
5.1.2 Subproblem
5.1.3 Objective functions of the relaxed problem
5.2 Preprocessing components
5.3 Overview of scheduling tool
5.4 Benchmark formulation
6 Test results
Entities | Number of |
---|---|
CMs | 2 |
CM-tasks | [3701, 2835] |
Fixed tasks | [2816, 1404] |
AMs | 2 |
AM-tasks | [1, 1] |
Dependencies | 1457 |
CN-messages | 64 |
Chains | 998 |
Entities | Number of |
---|---|
CMs | 5 |
CM-tasks | [5871, 2388, 2260, 1860, 1788] |
Fixed tasks | [2832, 1408, 1408, 1408, 584] |
AMs | 6 |
AM-tasks | [7, 3, 3, 2, (3, 1)] |
Dependencies | 11779 |
CN-messages | 96 |
Chains | 1458 |
Entities | Number of |
---|---|
CMs | 7 |
CM-tasks | [5871, 3867, 2388, 2260, 1860, 1860, 1788] |
Fixed tasks | [2832, 1452, 1408, 1408, 1408, 1408, 584] |
AMs | 8 |
AM-tasks | [7, 4, 3, 3, 2, 2, (3, 1)] |
Dependencies | 15155 |
CN-messages | 96 |
Chains | 2002 |
6.1 Preprocessing effect
Measurement | Instance | ||
---|---|---|---|
I | II | III | |
Complete number of y-variables |
\(22\times 10^6\)
|
\(52\times 10^6\)
|
\(70 \times 10^6\)
|
Reduction of task intervals by Alg. 2 |
\(5\%\)
|
\(18\%\)
|
\(17\%\)
|
Time for Alg. 2 | 27 s | 103 s | 123 s |
Number of y-variables after Algs. 2 and 3 |
\(0.2\times 10^6\)
|
\(0.9\times 10^6\)
|
\(1.2 \times 10^6\)
|
Reduction of v-variables by Alg. 4 |
\(47\%\)
|
\(90\%\)
|
\(92\%\)
|
6.2 Solution approach evaluation
Measurement | Instance | ||
---|---|---|---|
I | II | III | |
Number of sections |
\(2 \times 10^3\)
|
\(4 \times 10^3\)
|
\(6 \times 10^3\)
|
Number of \(\alpha \)-variables |
\(3 \times 10^4\)
|
\(11 \times 10^4\)
|
\(15 \times 10^4\)
|
Average number of \(\beta \)-variables in subproblem |
\(2 \times 10^3\)
|
\(6 \times 10^3\)
|
\(8 \times 10^3\)
|
Average number of y-variables in subproblem |
\(2 \times 10^4\)
|
\(5 \times 10^4\)
|
\(7 \times 10^4\)
|
-
The time limit in the relaxed problem is 8 h.
-
The relative MIP-gap in the relaxed problem is 0.10 for all runs.
-
The time limit in the subproblem is initially 2 h, and whenever an improved integer solution is found, it is reset to 4 h.
-
The relative MIP-gap in the subproblem is 0. This strict gap is required to ensure that all tasks are successfully sequenced.
-
The value of \(M_{\varDelta }\) is 1000.
-
In an iteration, at most 5 new generated sequences are added to the relaxed problem and the subproblem. If more than 5 sequences are generated, 5 of them are chosen at random.
Measurement | Section-slack | Centre-task | ||
---|---|---|---|---|
\(\varDelta =0.10\)
|
\(\varDelta =0.50\)
|
\(\varDelta =0.75\)
| ||
Total time | 164 | 243 | 467 | 182 |
Iterations | 1 | 1 | 1 | 1 |
Generated sequences | – | – | – | – |
Time relaxed problem | 6 | 31 | 23 | 23 |
Time subproblem | 1 | 53 | 283 | 2 |
Measurement | Section-slack | Centre-task | ||
---|---|---|---|---|
\(\varDelta =0.10\)
|
\(\varDelta =0.50\)
|
\(\varDelta =0.75\)
| ||
Total time | 1025 | 29676 | 2484 | 1623 |
Iterations | 1 | 1 | 1 | 1 |
Generated sequences | – | – | – | – |
Time relaxed problem | 111 | 28800 | 946 | 483 |
Time subproblem | 449 | 416 | 1081 | 680 |
Measurement | Section-slack | Centre-task | ||
---|---|---|---|---|
\(\varDelta =0.10\)
|
\(\varDelta =0.50\)
|
\(\varDelta =0.75\)
| ||
Total time | 2438 | 52269 | 7882 | 2210 |
Iterations | 4 | 3 | 2 | 1 |
Generated sequences | [14, 9, 4] | [1, 1] | 1 | – |
Time relaxed problem | [178, 33, 36, 82] | [28800, 41, 195] | [503, 34] | 569 |
Time subproblem | [30, 38, 33, 356] | [49, 15609, 6294] | [42, 6369] | 1079 |