Job selection and sequencing on a single machine in a random environment

The authors examine a single machine scheduling problem with random processing times and deadline. Given a set of independent jobs having specified initiation costs and terminal revenues, the objective is to select a subset of the jobs and sequence the selected jobs such that the expected profit is maximized. The job selection aspect considered by us marks a clear departure from the pure sequencing focus found in the traditional scheduling literature. In this paper, the authors assume an exponentially distributed deadline and do not allow preemption. Even under these conditions, the selection and sequencing problem remains quite difficult (unlike its pure sequencing counterpart); they in fact conjecture that the problem is NP-hard. However, they show that the problem can be efficiently solved as long as the cost parameter is agreeable or an approximate solution is acceptable. To this end, they descripte several solution properties, present dynamic programming algorithms (one of which exhibits a pseudo-polynomial time worst-case complexity), and propose a fully-polynomial time approximation scheme. In addition, the authors study a number of special cases which can be solved in pllynomial time. Finally, they present the present work and discuss an extension where the jobs are precedence related.