# 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

 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 III There is also formula which you can use to calculate the number of permutations: nPr = n! / (n-r)! 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) -----------------------------------------------------------------

 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 -----------------------------------------------------------------

 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 VII (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. -----------------------------------------------------------------