Single machine scheduling with learning effect considerations

被引：278

作者：

Cheng, TCE ^{[1
]}

Wang, GQ

机构：

[1] Hong Kong Polytech Univ, Dept Management, Kowloon, Hong Kong, Peoples R China

[2] Hong Kong Polytech Univ, Dept Management, Kowloon, Hong Kong, Peoples R China

[3] Jinan Univ, Dept Business Adm, Guangzhou, Peoples R China

来源：

ANNALS OF OPERATIONS RESEARCH | 2000年 / 98卷 / 1-4期

关键词：

scheduling; sequencing; learning;

D O I：

10.1023/A:1019216726076

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we study a single machine scheduling problem in which the job processing times will decrease as a result of learning. A volume-dependent piecewise linear processing time function is used to model the learning effects. The objective is to minimize the maximum lateness. We first show that the problem is NP-hard in the strong sense and then identify two special cases which are polynomially solvable. We also propose two heuristics and analyse their worst-case performance.

引用

页码：273 / 290

页数：18

共 22 条

[1]

ALDER GL, 1973, THESIS NEW YORK U

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

Buffa E. S., 1984, Meeting the competitive challenge: Manufacturing strategy for US companies

[4]

Cheng TCE, 1994, 0694 HONG KONG POL U

[5]

Corlett E.N., 1970, PERS MANAG, V2, P14

[6]

Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117

[7]

Gawiejnowicz S, 1996, INFORMATION PROCESSI, V56, P297

[8]

Graham R. L., 1979, Discrete Optimisation, P287

[9]

Greene T. J., 1984, Journal of Operations Management, V4, P85

[10]

HANCOCK WM, 1967, J IND ENGINEERING, V18, P42

← 1 2 3 →