Order scheduling in an environment with dedicated resources in parallel

被引:75
作者
Leung, JYT [1 ]
Li, HB
Pinedo, M
机构
[1] New Jersey Inst Technol, Dept Comp Sci, Newark, NJ 07102 USA
[2] NYU, Stern Sch Business, New York, NY 10012 USA
基金
美国国家科学基金会;
关键词
order scheduling; total completion time; NP-hard; approximation; Tabu Search;
D O I
10.1007/s10951-005-2860-x
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
We consider in machines in parallel with each machine capable of producing one specific product type. There are n orders with each one requesting specific quantities of the various different product types. Order j may have a release date r(j) and a due date d(j). The different product types for order j can be produced at the same time. We consider the class of objectives Sigma f(j)(C(j)) that includes objectives such as the total weighted completion time Sigma w(j) C(j) and the total weighted tardiness Sigma w(j) T(j) of the n orders. We present structural properties of the various problems and a complexity result. In particular, we show that minimizing F Cj when m >= 3 is strongly NP-hard. We introduce two new heuristics for the Sigma C(j) objective. An empirical analysis shows that our heuristics outperform all heuristics that have been proposed for this problem in the literature.
引用
收藏
页码:355 / 386
页数:32
相关论文
共 17 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]  
[Anonymous], 1997, TABU SEARCH
[3]  
BARNES JW, 1995, OPERAT RES COMP SCI, V3, P101
[4]   MINIMIZING TOTAL TARDINESS ON ONE MACHINE IS NP-HARD [J].
DU, JZ ;
LEUNG, JYT .
MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) :483-495
[5]   ONE-MACHINE SEQUENCING TO MINIMIZE CERTAIN FUNCTIONS OF JOB TARDINESS [J].
EMMONS, H .
OPERATIONS RESEARCH, 1969, 17 (04) :701-&
[6]  
Graham R. L., 1979, Discrete Optimisation, P287
[7]  
Julien F. M., 1990, Journal of Manufacturing and Operations Management, V3, P177
[8]  
LAGUNA M, 2004, IMPLEMENTING TESTING
[9]  
LEUNG JYT, 2005, EUROPEAN J OPERATION, V163, P567
[10]  
Li H., 2005, THESIS NEW JERSEY I