logo for solving-math-problems.com
leftimage for solving-math-problems.com

Scheduling and Permutations

by Jennifer
(Michigan)











































Matthew works as a computer operator at a small university.

One evening he finds that 12 computer programs have been
submitted earlier that day for batch processing.

In how many ways can Matthew order the processing of these programs if:

(a) there are no restrictions?

(b) he considers four of the programs higher in priority than the other eight and wants to process
those four first?

(c) he first separates the programs into four of top priority, five of lesser priority, and three of least priority.

He wishes to process the 12 programs in such a way that the top-priority programs are processed first, and the three programs of least priority are processed last?

Comments for Scheduling and Permutations

Click here to add your own comments

Sep 08, 2013
Optimal Scheduling
by: Staff


Answer

Part I

Matthew works as a computer operator at a small university.

One evening he finds that 12 computer programs have been
submitted earlier that day for batch processing.

In how many ways can Matthew order the processing of these programs if:

(a) there are no restrictions?

The order of processing the programs does matter.

Processing all twelve programs in this order {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} is not the same as processing all twelve programs in this order {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}.

Calculating every possible way Matthew can order the processing is called calculating the number of permutations.

The number of permutations is the number of all the possible ways of choosing the sequential order the programs could be processed.

You have 12 choices of which program to process first, 11 choices of which program to process second, 10 choices for the third program to process, and so on.

The number of permutations can be calculated as follows:

P = 12
(first program to process: any one of the 12 programs can be chosen.)

× 11
(second program to process: since 1 program has already been selected for processing, the second selection can only be made from among the 11 remaining programs.)

× 10
(third program to process: since 2 programs have already been selected for processing, the third selection can only be made from among the 10 remaining programs.)

× 9
(fourth program to process: since 3 programs have already been selected for processing, the fourth selection can only be made from among the 9 remaining programs.)




-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff

-----------------------------------------------------------------


Part II

× 8
(fifth program to process: since 4 programs have already been selected for processing, the fourth selection can only be made from among the 8 remaining programs.)

× 7
(sixth program to process: since 5 programs have already been selected for processing, the sixth selection can only be made from among the 7 remaining programs.)

× 6
(seventh program to process: since 6 programs have already been selected for processing, the seventh selection can only be made from among the 6 remaining programs.)

× 5
(eighth program to process: since 7 programs have already been selected for processing, the eighth selection can only be made from among the 5 remaining programs.)

× 4
(ninth program to process: since 8 programs have already been selected for processing, the ninth selection can only be made from among the 4 remaining programs.)

× 3
(tenth program to process: since 9 programs have already been selected for processing, the tenth selection can only be made from among the 3 remaining programs.)

× 2
(eleventh program to process: since 10 programs have already been selected for processing, the eleventh selection can only be made from among the 2 remaining programs.)

× 1
(last program to process: since 11 programs have already been selected for processing, the twelfth selection is the only remaining program available.)



P = 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1


P = 12!

P = 479,001,600

There are 479 million, 1 thousand and 600 ways of ordering the processing of the 12 programs.



-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff


-----------------------------------------------------------------


Part III


There is also formula which you can use to calculate the number of permutations:


nPr = n! / (n-r)!


Permutations formula:  order is important, and repetition is not allowed.




n = number of elements in the set {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1} = 12

r = number of elements selected = 12 [r = 12 will be used since you are processing all 12]

0 ≤ r ≤ n

Order is important

Repetition is not allowed (you are not going to process the same program more than once)


Definitions: 

     n = number of elements in the set  {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1} = 12

     r = number of elements selected = 12 [r = 12 will be used since you are processing all 12]






-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff


-----------------------------------------------------------------


Part IV



12P12 = 12! / (12 - 12)!

12P12 = 12! / (0)!

12P12 = 12! / 1

12P12 = 12!, or 479,001,600


Calculate permutations when n = 12 and r = 12





Permutations:  part (a)








-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff


-----------------------------------------------------------------


Part V


(b) he considers four of the programs higher in priority than the other eight and wants to process
those four first?

You can think of this question in two stages:

Stage 1: Process the first four high priority programs.

Stage 2: Process the last eight programs.


The first four programs to process:

You have 4 choices of which program to process first, 3 choices of which program to process second, 2 choices for the third program, and 1 choice for the fourth program.

The number of permutations for the first four programs can be calculated as follows:

P = 4
(first program to process: any one of the 4 programs can be chosen.)

× 3
(second program to process: since 1 program has already been selected for processing, the second selection can only be made from among the 3 remaining programs.)

× 2
(third program to process: since 2 programs have already been selected for processing, the third selection can only be made from among the 2 remaining programs.)

× 1
(fourth program to process: since 3 programs have already been selected for processing, the fourth selection is the only remaining program.)



P = 4 × 3 × 2 × 1

P = 4!


The last eight programs to process:

You have 8 choices of which program to process first, 7 choices of which program to process second, 6 choices for the third program, and 3 choice for the fourth program, and so on.

The number of permutations for the last eight programs can be calculated as follows:

P = 8
(first program to process: any one of the 8 programs can be chosen.)

× 7
(second program to process: since 1 program has already been selected for processing, the second selection can only be made from among the 7 remaining programs.)




-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff


-----------------------------------------------------------------


Part VI


× 6
(third program to process: since 2 programs have already been selected for processing, the third selection can only be made from among the 6 remaining programs.)

× 5
(fourth program to process: since 3 programs have already been selected for processing, the fourth selection can only be made from among the 5 remaining programs.)

× 4
(fifth program to process: since 4 programs have already been selected for processing, the fifth selection can only be made from among the 4 remaining programs.)

× 3
(sixth program to process: since 5 programs have already been selected for processing, the sixth selection can only be made from among the 3 remaining programs.)

× 2
(seventh program to process: since 6 programs have already been selected for processing, the seventh selection can only be made from among the 2 remaining programs.)

× 1
(last program to process: since 7 programs have already been selected for processing, the eighth selection is the only remaining program available.)



P = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1

P = 8!


the final answer to question (b)

P = 4! × 8!

P = 24 × 40,320

P = 967,680






using the permutation formula:

nPr = n! / (n-r)!

P = 4P4 × 8P8

4P4 = 4! / (4 - 4)!

8P8 = 8! / (8 - 8)!

P = (4! / (4 - 4)!) × (8! / (8 - 8)!)


P = (4! / (0)!) × (8! / (0)!)


P = (4! / 1) × (8! / 1)

P = 4! × 8!

P = 24 × 40,320

P = 967,680






-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff


-----------------------------------------------------------------


Part VII



Calculate compound permutations when: 

      n = 4 and r = 4

      n = 8 and r = 8





Permutations:  part (b)





(c) he first separates the programs into four of top priority, five of lesser priority, and three of least priority.

He wishes to process the 12 programs in such a way that the top-priority programs are processed first, and the three programs of least priority are processed last?

You can think of this question in three stages:

Stage 1: Process the first four high priority programs.

Stage 2: Process the five programs of lesser priority.

Stage 3: Process the last three programs of least priority.




-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff


-----------------------------------------------------------------


Part VIII


The first four programs to process:

You have 4 choices of which program to process first, 3 choices of which program to process second, 2 choices for the third program, and 1 choice for the fourth program.

The number of permutations for the first four programs can be calculated as follows:

P = 4
(first program to process: any one of the 4 programs can be chosen.)

× 3
(second program to process: since 1 program has already been selected for processing, the second selection can only be made from among the 3 remaining programs.)

× 2
(third program to process: since 2 programs have already been selected for processing, the third selection can only be made from among the 2 remaining programs.)

× 1
(fourth program to process: since 3 programs have already been selected for processing, the fourth selection is the only remaining program.)



P = 4 × 3 × 2 × 1

P = 4!


Process the five programs of lesser priority:

P = 5
(first program to process: any one of the 5 programs can be chosen.)

× 4
(second program to process: since 1 program has already been selected for processing, the second selection can only be made from among the 4 remaining programs.)

× 3
(third program to process: since 2 programs have already been selected for processing, the third selection can only be made from among the 3 remaining programs.)

× 2
(fourth program to process: since 3 programs have already been selected for processing, the fourth selection can only be made from among the 2 remaining programs.)

× 1
(fifth program to process: since 4 programs have already been selected for processing, the fifth selection is the only remaining program.)




-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff


-----------------------------------------------------------------


Part IX


P = 5 × 4 × 3 × 2 × 1

P = 5!


Process the last three programs of least priority:

P = 3
(first program to process: any one of the 3 programs can be chosen.)

× 2
(second program to process: since 1 program has already been selected for processing, the second selection can only be made from among the 2 remaining programs.)

× 1
(last program to process: since 2 programs have already been selected for processing, the third selection is the only remaining program.)



P = 3 × 2 × 1

P = 3!


the final answer to question (c)

P = 4! × 5! × 3!

P = 24 × 120 × 6

P = 17,280




using the permutation formula:

nPr = n! / (n-r)!

P = 4P4 × 5P5 × 3P3

4P4 = 4! / (4 - 4)!

5P5 = 5! / (5 - 5)!

3P3 = 3! / (3 - 3)!


P = (4! / (4 - 4)!) × (5! / (5 - 5)!) × (3! / (3 - 3)!)


P = (4! / (0)!) × (5! / (0)!) × (3! / (0)!)


P = (4! / 1) × (5! / 1) × (3! / 1)


P = 4! × 5! × 3!

P = 24 × 120 × 6

P = 17,280


 Calculate compound permutations when: 

      n = 4 and r = 4

      n = 5 and r = 5

      n = 3 and r = 3






-----------------------------------------------------------------

Sep 08, 2013
Optimal Scheduling
by: Staff


-----------------------------------------------------------------


Part X



Permutations:  part (c)










Thanks for writing.

Staff
www.solving-math-problems.com



Click here to add your own comments

Join in and write your own page! It's easy to do. How? Simply click here to return to Math Questions & Comments - 01.



Copyright © 2008-2015. All rights reserved. Solving-Math-Problems.com