The complexity of scheduling problems grows as the number of objectives/criteria increase. While a majority of the multi criteria scheduling problems are known to be NP-Hard; near-optimal solution methods exist for quite a number of single criterion and bicriteria scheduling problems. This has encouraged researchers to explore the possibilities of reducing multi criteria scheduling problems to equivalent bicriteria problems. In this work, we demonstrate through experimentation that multi criteria scheduling problems can indeed be reduced to bicriteria scheduling problems. In order to demonstrate this, the multi criteria scheduling problem of simultaneously minimizing the total completion time, total flow time, total lateness, and number of tardy jobs on a single machine with release dates was explored. Three existing solution methods were tested on 950 randomly generated problems ranging from 3 to 100 jobs. Experimental results were provided while conclusions drawn based on the results.

Keywords: Multi-criteria, reducibility, bi-criteria, effectiveness, near-optimal