Роздрукувати сторінку
Главная \ Методичні вказівки \ Методичні вказівки \ 2357 Контрольная работа по дисциплине Теория расписаний

Контрольная работа по дисциплине Теория расписаний

« Назад

2357 Контрольная работа по дисциплине Теория расписаний

Контрольная работа по дисциплине «Теория расписаний» 

Задание 1

Привести (придумать) две содержательные постановки задач, сводящихся к нахождению оптимального расписания.

  1. В первой задаче длительности работ не должны зависеть от упорядочения работ;

  2. Во второй задаче длительности работ должны зависеть от упорядочения работ;     

В каждой задаче определить:

  • множество упорядочиваемых работ (в терминах предложенной предметной области);

  • отношения предшествования, которые наложены на работы (если они имеет место);

  • множество машин, на которых эти работы могут быть выполнены;

  • критерий оценки расписания.

Задание 2 

 Для системы /1 (согласно варианту) записать  математические выражения критериев, определить их регулярность/нерегулярность, составить оптимальные[1] расписания выполнения работ (сославшись при этом на формулировку соответствующей теоремы), построить диаграмму Гантта: 

  1. среднее время окончания;

  2. среднее время прохождения;

  3. среднее время ожидания;

  4. среднее время смещения;

  5. среднее взвешенное время окончания;

  6. среднее взвешенное время прохождения;

  7. среднее взвешенное время ожидания;

  8. среднее взвешенное время смещения;

  9. максимальное время окончания;

  10. максимальное время ожидания;

  11. максимальное время прохождения;

  12. минимальное время окончания;

  13. минимальное время ожидания;

  14. минимальное время прохождения;

  15. максимум смещения;

  16. максимум запаздывания;

  17. минимум смещения;

  18. минимум запаздывания;

  19. среднее время опережения;

  20. среднее время запаздывания;

  21. среднее взвешенное время опережения;

  22. среднее взвешенное время запаздывания; 

ti – длительность i-й работы;

di – директивный срок i-й работы;

ui – вес i-й работы. 

Задание 3 

Вариант 1.

Доказать теорему.

Теорема. Расписание в системе  (минимизация среднего времени окончания выполнения работ) оптимально, если после упорядочения длительности работ не убывают. 

Вариант 2.

Доказать теорему.

Теорема. Расписание в системе  (минимизация среднего временного смещения) оптимально, если после упорядочения длительности работ не убывают. 

Вариант 3.

Доказать теорему.

Теорема. Расписание в системе  (минимизация максимума запаздывания работ в системе) оптимально, если после упорядочения директивные сроки работ не убывают. 

Вариант 4.

Доказать теорему.

Теорема. Расписание в системе  (максимизация среднего времени  пребывания в системе) оптимально, если после упорядочения длительности работ не возрастают. 

Вариант 5.

Доказать теорему.

Теорема. Расписание в системе  (максимизация минимального запаздывания работ в системе) оптимально, если после упорядочения резервы работ не убывают. 

Вариант 6.

Доказать теорему.

Теорема. Расписание в системе  (минимизация среднего времени ожидания в системе) оптимально, если после упорядочения длительности работ не убывают. 

Вариант 7.

Доказать теорему.

Теорема. Расписание в системе  (максимизация среднего времени окончания выполнения работ) оптимально, если после упорядочения длительности работ не возрастают. 

Вариант 8.

Доказать теорему.

Теорема. Расписание в системе  (максимизация среднего временного смещения) оптимально, если после упорядочения длительности работ не возрастают. 

Вариант 9.

Доказать теорему.

Теорема. Расписание в системе n/1 (минимизация  средневзвешенного времени окончания работ в системе) оптимально, если после упорядочения  ... (продолжить формулировку теоремы самостоятельно). 

Вариант 10.

Доказать теорему.

Теорема. Расписание в системе  (максимизация средневзвешенного времени  пребывания в системе) оптимально, если после упорядочения ... (продолжить формулировку теоремы самостоятельно).  

Вариант 11.

Доказать теорему.

Теорема. Расписание в системе n/1 (максимизация  средневзвешенного ожидания в системе) оптимально, если после упорядочения ... (продолжить формулировку теоремы самостоятельно). 

Вариант 12.

Доказать теорему.

Теорема. Расписание в системе  (максимизация среднего времени  ожидания в системе) оптимально, если после упорядочения длительности работ не возрастают. 

Вариант 13.

Доказать теорему.

Теорема. Расписание в системе  (минимизация средневзвешенного времени  смещения в системе) оптимально, если после упорядочения ... (продолжить формулировку теоремы самостоятельно). 

Вариант 14.

Доказать теорему.

Теорема. Расписание в системе n/1 (минимизация  средневзвешенного ожидания в системе) оптимально, если после упорядочения ... (продолжить формулировку теоремы самостоятельно). 

Вариант 15.

Доказать теорему.

Теорема. Расписание в системе n/1 (максимизация  средневзвешенного времени окончания работ в системе) оптимально, если после упорядочения ... (продолжить формулировку теоремы самостоятельно). 

Вариант 16.

Доказать теорему.

Теорема. Расписание в системе  (максимизация средневзвешенного времени  смещения в системе) оптимально, если после упорядочения ... (продолжить формулировку теоремы самостоятельно).  

Вариант 17.

Доказать теорему.

Теорема. Расписание в системе  (минимизация средневзвешенного времени  пребывания в системе) оптимально, если после упорядочения ... (продолжить формулировку теоремы самостоятельно).  

Задание 4

Для системы n/1 составить расписание с нулевым максимальным запаздыванием[2] и минимизирующее среднюю длительность прохождения работ. 

Вариант

Работы i

1

2

3

4

5

6

t1

d1

t2

d2

t3

d3

t4

d4

t5

d5

t6

d6

1

10

14

11

62

12

27

7

78

2

45

8

58

2

11

17

8

62

13

24

2

15

8

25

11

71

3

7

10

13

50

13

49

11

59

2

85

5

88

4

12

16

13

18

9

48

4

20

9

48

6

73

5

14

20

13

77

11

24

7

13

10

35

8

13

6

12

37

7

72

13

59

14

64

13

65

11

28

7

12

85

7

89

3

39

10

55

12

15

9

70

8

13

71

7

70

6

7

9

30

4

82

6

37

9

6

13

7

41

12

13

9

52

11

80

12

43

10

6

83

3

7

7

48

3

37

14

52

5

70

11

9

72

10

44

7

84

11

37

7

65

5

38

12

12

37

10

81

12

37

5

68

10

83

8

65

13

14

88

11

54

11

45

11

25

2

89

5

37

14

9

75

10

38

12

75

10

76

13

46

11

40

15

10

38

11

53

9

54

5

79

2

42

13

13

16

8

70

6

38

11

37

13

79

8

83

13

58

17

9

88

3

17

14

72

9

28

10

25

12

84

18

8

60

7

26

8

47

13

57

6

46

11

20

19

14

88

3

69

14

70

13

33

14

24

6

65

20

12

70

13

27

6

33

14

67

12

21

9

72

21

9

20

2

63

8

35

12

53

4

45

11

76

22

13

81

6

18

10

31

5

83

13

42

3

37

23

14

47

5

13

10

35

14

88

6

56

8

10

24

14

49

9

24

7

78

12

78

13

74

6

38

25

14

49

11

41

13

87

7

81

6

33

13

77

26

9

56

9

37

11

57

9

34

8

32

13

64

27

9

48

8

76

7

35

5

24

14

71

10

41

28

6

60

9

58

12

12

8

88

4

77

4

86

29

9

87

8

9

13

16

12

87

7

30

3

87

30

6

87

8

45

12

22

10

88

5

15

9

33

31

5

56

8

26

13

55

12

31

4

73

10

56

32

12

45

9

52

2

24

3

61

10

12

3

47

33

13

80

13

28

13

22

3

42

14

58

12

72

34

10

43

11

55

7

73

10

86

8

83

9

72

35

14

69

10

33

13

52

13

45

9

67

7

67

36

8

24

8

18

11

44

2

27

6

38

12

78

37

9

13

8

32

4

11

8

61

4

13

7

79

38

6

35

5

48

13

45

10

66

9

49

13

64

39

9

68

13

50

11

53

11

35

10

46

10

28

40

12

73

13

29

7

34

6

17

10

36

12

13

ti – длительность i-й работы;

di – директивный срок i-й работы.

Задание 5

Составить расписание выполнения n=6 работ одной машиной, минимизирующее среднее взвешенное время запаздывания (алгоритм Шилда-Фридмана).

Для всех расписаний (промежуточных и окончательного) считать значение критерия. Достаточное число итераций – 2. 

Варианты

Работа

Параметры работы

1

2

3

4

5

6

1

ti

5

2

2

3

6

9

ui

5

1

2

1

3

1

ai

17

8

1

20

10

27

2

ti

5

2

4

3

4

3

ui

5

2

2

3

1

1

ai

19

5

11

3

10

14

3

ti

5

2

2

3

4

3

ui

5

1

2

3

1

1

ai

22

8

4

3

10

14

4

ti

7

2

6

2

4

1

ui

7

1

3

2

1

1

ai

16

2

3

7

10

2

5

ti

3

2

8

8

4

1

ui

1

1

8

2

2

1

ai

7

13

24

14

12

1

6

ti

5

13

8

4

9

6

ui

1

13

8

2

1

6

ai

13

66

24

14

22

6

7

ti

5

3

8

2

9

1

ui

1

3

2

2

1

1

ai

19

6

14

4

21

7

8

ti

3

2

8

2

4

1

ui

1

1

8

2

1

1

ai

8

13

24

7

12

2

9

ti

10

3

5

6

9

3

ui

2

1

1

3

9

3

ai

30

12

35

18

14

6

10

ti

10

2

2

6

9

9

ui

2

1

2

3

9

1

ai

30

8

1

18

14

27

11

ti

3

2

5

2

4

1

ui

3

1

1

2

1

1

ai

6

6

15

7

10

2

12

ti

3

2

2

4

6

6

ui

1

1

2

2

3

6

ai

9

8

3

14

22

6

13

ti

2

13

6

4

6

2

ui

2

13

6

2

3

1

ai

21

13

6

21

35

23

14

ti

6

12

4

2

2

8

ui

2

3

4

1

2

2

ai

14

30

5

7

2

22

15

ti

2

6

3

4

3

4

ui

1

2

3

1

1

2

ai

12

14

2

16

10

6

16

ti

18

2

12

4

10

3

ui

3

2

2

1

2

1

ai

30

8

20

6

7

4

17

ti

3

10

8

2

9

9

ui

3

2

2

2

1

1

ai

6

19

14

2

21

17

18

ti

5

2

2

8

4

1

ui

5

2

2

2

1

1

ai

17

5

4

10

12

2

19

ti

4

6

3

4

3

6

ui

2

2

3

1

1

6

ai

13

14

4

11

17

6

20

ti

10

2

8

6

9

1

ui

2

1

2

3

9

1

ai

22

8

14

7

14

27

21

ti

7

4

6

10

4

6

ui

7

2

2

2

1

1

ai

22

8

13

37

14

27

22

ti

6

2

3

4

5

1

ui

6

2

3

4

5

1

ai

21

5

14

3

22

6

23

ti

12

4

3

8

2

2

ui

6

2

1

8

1

2

ai

21

14

4

30

5

16

24

ti

1

3

4

8

7

6

ui

1

1

2

8

1

2

ai

1

14

7

22

14

7

25

ti

10

6

12

4

9

3

ui

2

2

2

1

9

1

ai

30

18

30

6

7

16

26

ti

4

12

2

6

5

10

ui

2

3

1

3

1

5

ai

10

19

4

7

21

14

27

ti

10

6

3

4

2

5

ui

2

2

3

1

1

5

ai

18

18

16

4

15

5

28

ti

5

2

6

4

2

10

ui

1

2

3

4

1

5

ai

8

8

16

5

15

11

29

ti

3

14

6

4

5

6

ui

1

7

3

2

5

6

ai

13

26

24

14

10

9

30

ti

10

4

11

4

2

5

ui

5

2

11

1

2

5

ai

31

8

16

15

7

15

Задание 6

Для одной машины составить расписание выполнения работ, минимизирующее среднюю длительность прохождения работ:

a) при условии, что работы частично упорядочены (цепочки не могут  разрываться);

b) при условии, что для работ задано отношение предшествования (цепочки могут  разрываться).

Для каждого из случаев вычислить значение критерия (среднюю длительность прохождения работ). 

Пример 1.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/1  1.2/8  1.3/2 

цепочка 2:   2.1/7  2.2/3  2.3/2  2.4/4 

цепочка 3:   3.1/1  3.2/5  3.3/1  3.4/8 

цепочка 4:   4.1/3  4.2/9  4.3/4  

Пример 2.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/3  1.2/7  1.3/8  1.4/7  1.5/3  1.6/2 

цепочка 2:   2.1/5  2.2/3  2.3/8  2.4/3 

цепочка 3:   3.1/2  3.2/8  3.3/3  3.4/7 

цепочка 4:   4.1/5  4.2/8  4.3/8  4.4/1  4.5/2  4.6/2  

Пример 3.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/1  1.2/6  1.3/1  1.4/7  1.5/6 

цепочка 2:   2.1/7  2.2/6  2.3/2  2.4/7  2.5/6  2.6/9 

цепочка 3:   3.1/9  3.2/3  3.3/7  3.4/3  3.5/1 

цепочка 4:   4.1/5  4.2/8  4.3/5  4.4/6  4.5/9  4.6/7  

Пример 4.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/1  1.2/7  1.3/9  1.4/7 

цепочка 2:   2.1/2  2.2/2  2.3/9  2.4/8  2.5/6 

цепочка 3:   3.1/7  3.2/3  3.3/1  3.4/6  3.5/3  3.6/8 

цепочка 4:   4.1/3  4.2/5  4.3/9  

Пример 5.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/2  1.2/3  1.3/2 

цепочка 2:   2.1/5  2.2/3  2.3/2  2.4/6  2.5/7 

цепочка 3:   3.1/1  3.2/1  3.3/1  3.4/1  3.5/8 

цепочка 4:   4.1/4  4.2/6  4.3/4  4.4/7  4.5/5  4.6/4  

Пример 6.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/8  1.2/2  1.3/1  1.4/1  1.5/1  1.6/2 

цепочка 2:   2.1/3  2.2/6  2.3/3  2.4/4  2.5/8 

цепочка 3:   3.1/3  3.2/6  3.3/7  3.4/9 

цепочка 4:   4.1/5  4.2/3  4.3/7  4.4/7  

Пример 7.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/7  1.2/4  1.3/5  1.4/6  1.5/8 

цепочка 2:   2.1/2  2.2/5  2.3/4  2.4/2  2.5/1 

цепочка 3:   3.1/7  3.2/1  3.3/9  3.4/8  3.5/7 

цепочка 4:   4.1/3  4.2/7  4.3/7  4.4/5  4.5/6  4.6/2  

Пример 8.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/9  1.2/4  1.3/2 

цепочка 2:   2.1/3  2.2/1  2.3/1  2.4/8  2.5/5  2.6/7 

цепочка 3:   3.1/7  3.2/1  3.3/3 

цепочка 4:   4.1/5  4.2/3  4.3/4  4.4/9  4.5/4  4.6/4  

Пример 9.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/1  1.2/8  1.3/7  1.4/2 

цепочка 2:   2.1/5  2.2/2  2.3/9  2.4/4  2.5/2  2.6/8 

цепочка 3:   3.1/1  3.2/6  3.3/9  3.4/5  3.5/3 

цепочка 4:   4.1/3  4.2/2  4.3/7  4.4/9  

Пример 10.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/7  1.2/5  1.3/1  1.4/7  1.5/2 

цепочка 2:   2.1/8  2.2/7  2.3/4 

цепочка 3:   3.1/2  3.2/1  3.3/2  3.4/1  3.5/4  3.6/4 

цепочка 4:   4.1/1  4.2/5  4.3/5  4.4/5  

Пример 11.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/8  1.2/6  1.3/3  1.4/4  1.5/6 

цепочка 2:   2.1/6  2.2/3  2.3/7  2.4/6  2.5/8  2.6/4 

цепочка 3:   3.1/6  3.2/8  3.3/5  3.4/2 

цепочка 4:   4.1/8  4.2/7  4.3/9  4.4/2  4.5/7  

Пример 12.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/3  1.2/7  1.3/5  1.4/9 

цепочка 2:   2.1/1  2.2/3  2.3/9 

цепочка 3:   3.1/8  3.2/7  3.3/9  3.4/3 

цепочка 4:   4.1/8  4.2/1  4.3/3  4.4/1  

Пример 13.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/4  1.2/1  1.3/2  1.4/7  1.5/3 

цепочка 2:   2.1/5  2.2/3  2.3/2  2.4/3 

цепочка 3:   3.1/7  3.2/3  3.3/8 

цепочка 4:   4.1/6  4.2/9  4.3/1  4.4/3  4.5/8  

Пример 13.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/4  1.2/1  1.3/2  1.4/7  1.5/3 

цепочка 2:   2.1/5  2.2/3  2.3/2  2.4/3 

цепочка 3:   3.1/7  3.2/3  3.3/8 

цепочка 4:   4.1/6  4.2/9  4.3/1  4.4/3  4.5/8  

Пример 15.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/1  1.2/9  1.3/2  1.4/1 

цепочка 2:   2.1/1  2.2/8  2.3/9 

цепочка 3:   3.1/2  3.2/7  3.3/9 

цепочка 4:   4.1/1  4.2/6  4.3/8  4.4/9  

Пример 16.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/6  1.2/9  1.3/7  1.4/7  1.5/9 

цепочка 2:   2.1/7  2.2/8  2.3/1  2.4/4  2.5/3  2.6/1 

цепочка 3:   3.1/3  3.2/8  3.3/9  3.4/1  3.5/9  3.6/9 

цепочка 4:   4.1/7  4.2/4  4.3/4  4.4/7  

Пример 17.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/4  1.2/6  1.3/5  1.4/9  1.5/1 

цепочка 2:   2.1/1  2.2/6  2.3/4  2.4/5  2.5/6  2.6/8 

цепочка 3:   3.1/9  3.2/5  3.3/5  3.4/9  3.5/3 

цепочка 4:   4.1/4  4.2/7  4.3/7  

Пример 18.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/6  1.2/8  1.3/5 

цепочка 2:   2.1/6  2.2/1  2.3/9 

цепочка 3:   3.1/8  3.2/4  3.3/1  3.4/2  3.5/6  3.6/8 

цепочка 4:   4.1/5  4.2/9  4.3/8  

Пример 19.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/7  1.2/9  1.3/2  1.4/2  1.5/6  1.6/8 

цепочка 2:   2.1/1  2.2/8  2.3/6 

цепочка 3:   3.1/4  3.2/2  3.3/8  3.4/8 

цепочка 4:   4.1/6  4.2/8  4.3/2  

Пример 20.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/4  1.2/5  1.3/7  1.4/8 

цепочка 2:   2.1/1  2.2/6  2.3/3  2.4/1 

цепочка 3:   3.1/2  3.2/1  3.3/6  3.4/8 

цепочка 4:   4.1/3  4.2/5  4.3/9  4.4/7  

Пример 21.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/1  1.2/8  1.3/3  1.4/1 

цепочка 2:   2.1/8  2.2/8  2.3/4  2.4/3 

цепочка 3:   3.1/4  3.2/6  3.3/4  3.4/6 

цепочка 4:   4.1/8  4.2/5  4.3/5  4.4/6  4.5/3  4.6/3  

Пример 22.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/1  1.2/8  1.3/3  1.4/1 

цепочка 2:   2.1/8  2.2/8  2.3/4  2.4/3 

цепочка 3:   3.1/4  3.2/6  3.3/4  3.4/6 

цепочка 4:   4.1/8  4.2/5  4.3/5  4.4/6  4.5/3  4.6/3  

Пример 23.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/5  1.2/2  1.3/3 

цепочка 2:   2.1/8  2.2/8  2.3/2  2.4/2  2.5/7 

цепочка 3:   3.1/4  3.2/3  3.3/1  3.4/9 

цепочка 4:   4.1/1  4.2/6  4.3/1  4.4/6  4.5/6  

Пример 24.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/2  1.2/9  1.3/8  1.4/6  1.5/5  1.6/8 

цепочка 2:   2.1/2  2.2/4  2.3/9  2.4/5  2.5/8 

цепочка 3:   3.1/3  3.2/6  3.3/1  3.4/4  3.5/4 

цепочка 4:   4.1/6  4.2/9  4.3/7  4.4/7  

Пример 25.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/4  1.2/1  1.3/4  1.4/3  1.5/9  1.6/3 

цепочка 2:   2.1/1  2.2/5  2.3/5  2.4/5 

цепочка 3:   3.1/2  3.2/4  3.3/9 

цепочка 4:   4.1/6  4.2/4  4.3/4  4.4/8  4.5/9  

Пример 26.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/6  1.2/5  1.3/9  1.4/3  1.5/1 

цепочка 2:   2.1/5  2.2/9  2.3/2  2.4/8  2.5/1  2.6/4 

цепочка 3:   3.1/9  3.2/4  3.3/7 

цепочка 4:   4.1/8  4.2/4  4.3/6  4.4/3  4.5/8  4.6/2  

Пример 27.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/4  1.2/1  1.3/9  1.4/1 

цепочка 2:   2.1/1  2.2/1  2.3/6 

цепочка 3:   3.1/8  3.2/2  3.3/7  3.4/4 

цепочка 4:   4.1/5  4.2/1  4.3/9  4.4/3  

Пример 28.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/3  1.2/8  1.3/8  1.4/4  1.5/5  1.6/3 

цепочка 2:   2.1/4  2.2/4  2.3/4  2.4/9  2.5/4 

цепочка 3:   3.1/7  3.2/5  3.3/2  3.4/3  3.5/4 

цепочка 4:   4.1/4  4.2/5  4.3/1  4.4/2  

Пример 29.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/5  1.2/5  1.3/9  1.4/8  1.5/6  1.6/4 

цепочка 2:   2.1/8  2.2/6  2.3/3  2.4/6 

цепочка 3:   3.1/3  3.2/6  3.3/1  3.4/5  3.5/8  3.6/8 

цепочка 4:   4.1/9  4.2/7  4.3/7  

Пример 30.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/9  1.2/3  1.3/5  1.4/4 

цепочка 2:   2.1/6  2.2/1  2.3/4  2.4/3  2.5/5  2.6/5 

цепочка 3:   3.1/5  3.2/6  3.3/4  3.4/6 

цепочка 4:   4.1/7  4.2/2  4.3/9  4.4/4  4.5/7  4.6/6  

Пример 31.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/5  1.2/7  1.3/9  1.4/5  1.5/6 

цепочка 2:   2.1/4  2.2/1  2.3/9  2.4/1  2.5/7  2.6/9 

цепочка 3:   3.1/6  3.2/9  3.3/8  3.4/1 

цепочка 4:   4.1/4  4.2/8  4.3/2  

Пример 32.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/6  1.2/9  1.3/8  1.4/4  1.5/1  1.6/1 

цепочка 2:   2.1/8  2.2/5  2.3/5  2.4/7  2.5/9 

цепочка 3:   3.1/2  3.2/2  3.3/9  3.4/2 

цепочка 4:   4.1/2  4.2/4  4.3/5  4.4/1  

Пример 33.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/3  1.2/3  1.3/1  1.4/3 

цепочка 2:   2.1/3  2.2/4  2.3/6  2.4/1  2.5/3  2.6/4 

цепочка 3:   3.1/7  3.2/4  3.3/1 

цепочка 4:   4.1/5  4.2/4  4.3/7  4.4/1  4.5/1  

Пример 34.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/5  1.2/8  1.3/6 

цепочка 2:   2.1/8  2.2/5  2.3/5  2.4/1 

цепочка 3:   3.1/7  3.2/4  3.3/3  3.4/6  3.5/4 

цепочка 4:   4.1/8  4.2/6  4.3/8  

Пример 35.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/7  1.2/7  1.3/8 

цепочка 2:   2.1/8  2.2/8  2.3/9  2.4/1 

цепочка 3:   3.1/5  3.2/7  3.3/8  3.4/5 

цепочка 4:   4.1/2  4.2/9  4.3/5  4.4/2  

Пример 37.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/4  1.2/7  1.3/9  1.4/4  1.5/1  1.6/7 

цепочка 2:   2.1/6  2.2/6  2.3/9 

цепочка 3:   3.1/7  3.2/3  3.3/6  3.4/8  3.5/3 

цепочка 4:   4.1/1  4.2/4  4.3/1  4.4/3  

Пример 38.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/2  1.2/1  1.3/8  1.4/4  1.5/2  1.6/3 

цепочка 2:   2.1/9  2.2/4  2.3/2  2.4/2 

цепочка 3:   3.1/3  3.2/4  3.3/6  3.4/8  3.5/8 

цепочка 4:   4.1/7  4.2/7  4.3/7  

Пример 39.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/4  1.2/3  1.3/9 

цепочка 2:   2.1/2  2.2/3  2.3/1  2.4/8 

цепочка 3:   3.1/1  3.2/2  3.3/5  3.4/3  3.5/6  3.6/5 

цепочка 4:   4.1/5  4.2/8  4.3/2  4.4/7  4.5/3  

Пример 40.

Упорядочить следующую совокупность работ 

цепочка 1:   1.1/8  1.2/9  1.3/1 

цепочка 2:   2.1/9  2.2/7  2.3/2  2.4/4 

цепочка 3:   3.1/4  3.2/8  3.3/8  3.4/4 

цепочка 4:   4.1/6  4.2/1  4.3/8  4.4/6  4.5/4  4.6/9 

[1] Для некоторых критериев пока не известен полиномиальный алгоритм решения задачи. В этом случае только доказывается регулярность (нерегулярность) критерия.

[2] Если после упорядочения по директивным срокам не получается расписание с нулевым максимальным запаздыванием, то нужно соответствующим образом изменить числовые характеристики работ (согласовав это с преподавателем)

З повагою ІЦ "KURSOVIKS"!