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

被引:16
作者
DE, P [1 ]
GHOSH, JB [1 ]
WELLS, CE [1 ]
机构
[1] UNIV DAYTON,DEPT MIS & DECIS SCI,DAYTON,OH 45469
关键词
STOCHASTIC SCHEDULING; MATHEMATICAL PROGRAMMING; SINGLE MACHINE; SELECTION AND SEQUENCING;
D O I
10.1016/0377-2217(93)90252-I
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We 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, we 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); we in fact conjecture that the problem is NP-hard. However, we 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, we describe 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, 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 precedence related.
引用
收藏
页码:425 / 431
页数:7
相关论文
共 12 条
[1]   N-JOB, ONE MACHINE SEQUENCING PROBLEMS UNDER UNCERTAINTY [J].
BLAU, RA .
MANAGEMENT SCIENCE SERIES A-THEORY, 1973, 20 (01) :101-109
[2]   MINIMIZING THE EXPECTED WEIGHTED NUMBER OF TARDY JOBS IN STOCHASTIC FLOW SHOPS [J].
BOXMA, OJ ;
FORST, FG .
OPERATIONS RESEARCH LETTERS, 1986, 5 (03) :119-126
[3]   ON THE MINIMIZATION OF THE WEIGHTED NUMBER OF TARDY JOBS WITH RANDOM PROCESSING TIMES AND DEADLINE [J].
DE, P ;
GHOSH, JB ;
WELLS, CE .
COMPUTERS & OPERATIONS RESEARCH, 1991, 18 (05) :457-463
[4]  
Garey MR., 1979, COMPUTERS INTRACTABI
[5]  
GITTINS J, 1982, DETERMINISTIC STOCHA, P125
[6]   ON SINGLE-MACHINE SCHEDULING WITH PRECEDENCE RELATIONS AND LINEAR OR DISCOUNTED COSTS [J].
GLAZEBROOK, KD ;
GITTINS, JC .
OPERATIONS RESEARCH, 1981, 29 (01) :161-173
[7]   PROJECT SELECTION AND SEQUENCING TO MAXIMIZE NET PRESENT VALUE OF THE TOTAL RETURN [J].
GUPTA, SK ;
KYPARISIS, J ;
IP, CM .
MANAGEMENT SCIENCE, 1992, 38 (05) :751-752
[8]   A DYNAMIC PROGRAMMING APPROACH TO SEQUENCING PROBLEMS [J].
HELD, M ;
KARP, RM .
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1962, 10 (01) :196-210
[9]  
Horowitz E., 1978, FUNDAMENTALS COMPUTE
[10]   OPTIMAL STRATEGIES FOR A CLASS OF CONSTRAINED SEQUENTIAL PROBLEMS [J].
KADANE, JB ;
SIMON, HA .
ANNALS OF STATISTICS, 1977, 5 (02) :237-255