Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms

被引：167

作者：

Damodaran, Purushothaman ^{[1
]}

Manjeshwar, Praveen Kumar ^{[1
]}

Srihari, Krishnaswami ^{[1
]}

机构：

[1] SUNY Binghamton, Dept Syst Sci & Ind Engn, Elect Mfg Res & Serv, Binghamton, NY 13902 USA

来源：

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS | 2006年 / 103卷 / 02期

关键词：

heuristics; batch-processing machines; scheduling; genetic algorithms;

D O I：

10.1016/j.ijpe.2006.02.010

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This paper aims at minimizing the makespan for a batch-processing machine. The processing times and the sizes of the jobs are known. The machine can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time of all the jobs in that batch. This problem is NP-hard and hence a genetic algorithm (GA) approach is proposed. Random instances were used to test the effectiveness of the proposed approach. The results obtained from GA were compared with a simulated annealing approach and a commercial solver. The results indicate that the GA was able to arrive at better makespan with shorter run times. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：882 / 891

页数：10

共 23 条

[1] Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure [J].

Dupont, L ;

Dhaenens-Flipo, C .

COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (07) :807-819

[2]

Ghazvini FJ, 1998, INT J PROD ECON, V55, P273, DOI 10.1016/S0925-5273(98)00067-X

[3] Scheduling semiconductor burn-in operations to minimize total flowtime [J].

Hochbaum, DS ;

Landy, D .

OPERATIONS RESEARCH, 1997, 45 (06) :874-885

[4] EFFICIENT SCHEDULING ALGORITHMS FOR A SINGLE BATCH PROCESSING MACHINE [J].

IKURA, Y ;

GIMPLE, M .

OPERATIONS RESEARCH LETTERS, 1986, 5 (02) :61-65

[5] Using genetic algorithms for single-machine bicriteria scheduling problems [J].

Köksalan, M ;

Keha, AB .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 145 (03) :543-556

[6] EFFICIENT ALGORITHMS FOR SCHEDULING SEMICONDUCTOR BURN-IN OPERATIONS [J].

LEE, CY ;

UZSOY, R ;

MARTINVEGA, LA .

OPERATIONS RESEARCH, 1992, 40 (04) :764-775

[7] Scheduling with agreeable release times and due dates on a batch processing machine [J].

Li, CL ;

Lee, CY .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 96 (03) :564-569

[8]

LI Y, 1998, INT J PROD ECON, V54, P55

[9] Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing [J].

Melouk, S ;

Damodaran, P ;

Chang, PY .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2004, 87 (02) :141-147

[10] The effect of various operators on the genetic search for large scheduling problems [J].

Nearchou, AC .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2004, 88 (02) :191-203

← 1 2 3 →