Suppose we are given a period during which the next product cycle is scheduled and there are n possible projects for selection. Assume that for each project, the project manager has estimated the number of weeks that the project is expected to take and marketing has estimated the expected increase in revenue as a result of implementing the project. In general, the total time required to complete all the projects is often far in excess of the time available. The questions is: How do we, as a first approximation, select which projects should be scheduled?

Selecting Projects

Testing all possible combinations of n projects may be prohibitively expensive. A backtracking algorithm may be more efficient; however, we will look at an 0(n ln(n)) greedy algorithm:

Greedy by Time

The critical component is the time constraint: with only a fixed period, it may be reasonable to attempt to fit the largest project first, followed by smaller projects. Such an algorithm would be termed greedy by time.

Greedy by Expected Revenue

The actual goal, however, is to maximize revenue; therefore, it may be a better idea to be greedy by revenue: select those projects which make the most money first and continue to schedule the next highest profitable project which still fits into the remaining time. Such an algorithm would be termed greedy by expected revenue.

Greedy by Revenue Density

A best idea, however, is to attempt to maximize the amount of revenue made per week of work. Thus, one would begin by scheduling that project which makes the most per week that the project is worked on. As a first approximation, this is better than either greedy by time or revenue as it weighs both the constraint (the time limit) and the desirable outcome (the expected revenue).

Example

As an example, consider the list of projects given in Table 1. Suppose we are given a 50 week product cycle and it is required that we chose a subset of these projects to schedule over the next year (assuming two weeks holiday per employee).

Project	Time (wk)	Revenue (1000$)
1	4	8
2	18	19
3	14	15
4	7	7
5	10	11
6	3	4
7	11	12
8	4	8
9	1	1
10	13	17
11	12	14
12	8	11
13	3	5
14	3	4
15	8	9
16	10	10
17	3	3
18	10	13
19	14	18
20	12	16

Greedy by time produces a list with Projects 2, 19, 3, and 1 for a total of $60 000 spanning 50 weeks.

Greedy by expected revenue produces a list with Projects 2, 19, 10, 1, and 9 for a total of $63 000 spanning 50 weeks.

Greedy by expected revenue density, however, chooses Projects 1, 8, 13, 12, 6, 14, 20, and 10 for a total of $73 000 spanning 50 weeks. In this example, this is the optimal solution; however, this is not always guaranteed to be the case.

Greedy by time or by expected revenue both focus on the single largest project, Project 2; however, the expected revenue per week worked on the project is only $1056.

Large Scale Examples

Figures 1 and 2 show the result of applying these strategies to finding the total expected revenue for 100 projects with uniformly randomly chosen times and expected revenues between 1 and 20. Because there is no correlation between time or revenue, greedy by time does the least to maximize the expected revenue with an average revenue of 50. Greedy by expected revenue does significantly better; however, in all cases, greedy by expected revenue density does best. This is clearly shown in Figure 2 which, for each set of projects, the expected revenue of each scheme is plotted against the other and there was not one case where even parity was met.

Figure 1. A plot of 800 trials of random times and expected revenues chosen in [1, 20] showing the projected total expected revenue of the three schemes plotted against each other.

Figure 2. The same 800 trials as in Figure 1; however, this figure only shows the projected total expected revenue of the greedy-by-expected-revenue plotted against the total expected revenue of the greedy-by-expected-revenue-density schemes.

Figure 3 shows how the three schemes work when there is a tighter correlation between revenue with the time randomly chosen between 4 and 23 with the expected revenue being ±3 of this value. Again, greedy-by-revenue-density always outperforms.

Figure 3. 800 trials of random times chosen in [4, 23] and expected revenue being within ±3 of the time. The plot shows the projected total expected revenue of the three schemes plotted against each other.

Final Comments

As a comment: there are many other requirements associated with project scheduling:

• The requirement for a banner project which may be used to market the resulting product;
• The probability of certain projects to fail;
• The requirement for a certain number of projects not to fail, or, at least, to have a very small probability of failure;
• The need to prepare for future projects;
• The personal interest of certain executive officers of the company; etc.