JOB SELECTION AND SEQUENCING ON A SINGLE-MACHINE IN A RANDOM ENVIRONMENT

We examine a single machine scheduling problem with random processing times and deadline. Given a set of independent jobs having specified i nitiation costs and terminal revenues, the objective is to select a su bset 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 traditio nal scheduling literature. In this paper, we assume an exponentially d istributed deadline and do not allow preemption. Even under these cond itions, the selection and sequencing problem remains quite difficult ( unlike its pure sequencing counterpart); we in fact conjecture that th e problem is NP-hard. However, we show that the problem can be efficie ntly solved as long as the cost parameter is agreeable or an approxima te solution is acceptable. To this end, we describe several solution p roperties, present dynamic programming algorithms (one of which exhibi ts a pseudo-polynomial time worst-case complexity), and propose a full y-polynomial time approximation scheme. In addition, we study a number of special cases which can be solved in polynomial time. Finally, we summarize our work and discuss an extension where the jobs are precede nce related.