Some clarifications on the bicriteria scheduling of unit execution time jobs on a single machine

In a recent paper, Chen and Bulfin have studied bicriteria scheduling of unit execution time jobs on a single machine for a number of commonly used criteria. They offer simple solutions for the cases when a value function defined over the two criteria is to be maximized, when the criteria themselves are to be hierarchically minimized, and when the criteria are to be simultaneously minimized. This note provides an interpretation of the Chen-Bulfin solution for the value function case, indicates that the solution may not be consistent with the traditional objective and shows how a consistent solution might be obtained. Furthermore, it points to several flaws in the Chen-Bulfin solution for the simultaneous minimization case (when a completely representative set of efficient schedules must be obtained), and shows how these flaws might be corrected.