P. De et al., JOB SELECTION AND SEQUENCING ON A SINGLE-MACHINE IN A RANDOM ENVIRONMENT, European journal of operational research, 70(3), 1993, pp. 425-431
Citations number
12
Categorie Soggetti
Management,"Operatione Research & Management Science
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.