学术探索
学术期刊
新闻热点
数据分析
智能评审

MINIMIZING LATE JOBS IN THE GENERAL ONE MACHINE SCHEDULING PROBLEM

被引：27
作者：
DAUZEREPERES, S
机构：
[1] Laboratory for Manufacturing and Productivity, Massachusetts Institute of Technology, Cambridge
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1995年 / 81卷 / 01期
关键词：
SCHEDULING THEORY; ONE-MACHINE SCHEDULING; LINEAR PROGRAMMING; LOWER BOUND; HEURISTICS;
D O I：
10.1016/0377-2217(94)00116-T
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, the problem of minimizing the number of late jobs on one machine is investigated. The general problem is considered, i.e., with release dates and different due dates. A lower bound is first proposed, based on the relaxation of a Mixed-Integer Linear Programming formulation of the problem. A heuristic is then presented. Its effectiveness is computationally studied by comparison with the lower bound.
引用
收藏
页码：134 / 142
页数：9
相关论文
共 9 条
[1]  
DAUZEREPERES S, 1993, LMP93011 MIT LAB MAN
[2]   FORMULATING THE SINGLE-MACHINE SEQUENCING PROBLEM WITH RELEASE DATES AS A MIXED INTEGER-PROGRAM [J].
DYER, ME ;
WOLSEY, LA .
DISCRETE APPLIED MATHEMATICS, 1990, 26 (2-3) :255-270
[3]   ON THE COMPLEXITY OF GENERALIZED DUE DATE SCHEDULING PROBLEMS [J].
HALL, NG ;
SETHI, SP ;
SRISKANDARAJAH, C .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 51 (01) :100-109
[4]   SCHEDULING PROBLEMS WITH GENERALIZED DUE DATES [J].
HALL, NG .
IIE TRANSACTIONS, 1986, 18 (02) :220-222
[5]   SOLVABLE CASE OF ONE-MACHINE SCHEDULING PROBLEM WITH READY AND DUE TIMES [J].
KISE, H ;
IBARAKI, T ;
MINE, H .
OPERATIONS RESEARCH, 1978, 26 (01) :121-126
[6]  
LASSERRE JB, 1992, 2ND IPCO C PITTSB
[7]  
Lawler E. L., 1993, HDB OPERATIONS RES M, V4
[8]   N JOB, ONE MACHINE SEQUENCING ALGORITHM FOR MINIMIZING THE NUMBER OF LATE JOBS [J].
MOORE, JM .
MANAGEMENT SCIENCE, 1968, 15 (01) :102-109
[9]   ALGORITHMS FOR SCHEDULING A SINGLE-MACHINE TO MINIMIZE THE WEIGHTED NUMBER OF LATE JOBS [J].
POTTS, CN ;
VANWASSENHOVE, LN .
MANAGEMENT SCIENCE, 1988, 34 (07) :843-858
1