Single machine scheduling to minimize the number of early and tardy jobs

被引：49
作者：
Lann, A
Mosheiov, G
机构：
[1] HEBREW UNIV JERUSALEM,SCH BUSINESS ADM,IL-91905 JERUSALEM,ISRAEL
[2] HEBREW UNIV JERUSALEM,DEPT STAT,IL-91905 JERUSALEM,ISRAEL
来源：
COMPUTERS & OPERATIONS RESEARCH | 1996年 / 23卷 / 08期
关键词：
D O I：
10.1016/0305-0548(95)00078-X
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We study single machine scheduling problems with the objective of minimizing the number of early and tardy jobs. Several cost structures are considered: job-independent, job-dependent and symmetric, and job-dependent and asymmetric. The first two problem-classes are shown to be polynomially solvable, whereas the latter is shown to be NP-hard, and heuristic solution methods are introduced. An extensive numerical study tests the performance of the proposed algorithms. Finally, separate treatment is given to the pre-emptive versions of the above models. (C) 1996 Elsevier Science Ltd
引用
收藏
页码：769 / 781
页数：13
相关论文
共 13 条
[1]   SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW [J].
BAKER, KR ;
SCUDDER, GD .
OPERATIONS RESEARCH, 1990, 38 (01) :22-36
[2]  
CHENG TCE, 1994, J OPER RES SOC, V45, P685, DOI 10.1057/jors.1994.106
[3]  
FEDERGRUEN A, 1993, NAV RES LOG, V40, P951, DOI 10.1002/1520-6750(199312)40:7<951::AID-NAV3220400707>3.0.CO
[4]  
2-1
[5]   GREEDY HEURISTICS FOR SINGLE-MACHINE SCHEDULING PROBLEMS WITH GENERAL EARLINESS AND TARDINESS COSTS [J].
FEDERGRUEN, A ;
MOSHEIOV, G .
OPERATIONS RESEARCH LETTERS, 1994, 16 (04) :199-208
[6]   ALGORITHM FOR SPACE-SHUTTLE SCHEDULING PROBLEM [J].
FISHER, ML ;
JAIKUMAR, R .
OPERATIONS RESEARCH, 1978, 26 (01) :166-182
[7]  
KARP R. M., 1972, COMPLEXITY COMPUTER, P85, DOI DOI 10.1007/978-1-4684-2001-2_9
[8]  
LANN A, 1994, SIMPLE MACHINE SCHED
[9]   FUNCTIONAL EQUATION AND ITS APPLICATION TO RESOURCE ALLOCATION AND SEQUENCING PROBLEMS [J].
LAWLER, EL ;
MOORE, JM .
MANAGEMENT SCIENCE SERIES A-THEORY, 1969, 16 (01) :77-84
[10]  
LAWLER EL, 1993, SEQUENCING SCHEDULIN
12