Minimizing makespan on parallel batch processing machines

被引：115

作者：

Chang, PY

Damodaran, P ^{[1
]}

Melouk, S

机构：

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

[2] Mingchi Inst Technol, Dept Ind Engn & Management, Taipei 243, Taiwan

[3] USAF, Inst Technol, Dept Operat Sci, Wright Patterson AFB, OH 45433 USA

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 2004年 / 42卷 / 19期

关键词：

D O I：

10.1080/00207540410001711863

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

A simulated annealing approach to minimize makespan for identical parallel batch-processing machines is presented. Each job has a corresponding processing time and size. The machine can process the jobs in batches as long as the total size of all the jobs in a batch does not exceed the machine capacity. The processing time of a batch is equal to the longest processing time among all the jobs in the batch. Random instances were generated to test the approach with respect to solution quality and run time. The results of the simulated annealing approach were compared with CPLEX. The approach outperforms CPLEX on most of the instances.

引用

页码：4211 / 4220

页数：10

共 27 条

[1] THE N-CITY TRAVELING SALESMAN PROBLEM - STATISTICAL-MECHANICS AND THE METROPOLIS ALGORITHM [J].

BONOMI, E ;

LUTTON, JL .

SIAM REVIEW, 1984, 26 (04) :551-568

[2] Batch scheduling with deadlines on parallel machines [J].

Brucker, P ;

Kovalyov, MY ;

Shafransky, YM ;

Werner, F .

ANNALS OF OPERATIONS RESEARCH, 1998, 83 (0) :23-40

[3]

BURKARD RE, 1984, J OPTIMIZATION THEOR, V45, P41

[4] THERMODYNAMICAL APPROACH TO THE TRAVELING SALESMAN PROBLEM - AN EFFICIENT SIMULATION ALGORITHM [J].

CERNY, V .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1985, 45 (01) :41-51

[5] MINIMIZING TOTAL COMPLETION-TIME ON A BATCH PROCESSING MACHINE WITH JOB FAMILIES [J].

CHANDRU, V ;

LEE, CY ;

UZSOY, R .

OPERATIONS RESEARCH LETTERS, 1993, 13 (02) :61-65

[6] 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

[7] SIMULATED ANNEALING - A TOOL FOR OPERATIONAL-RESEARCH [J].

EGLESE, RW .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 46 (03) :271-281

[8]

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

[9] USING SIMULATED ANNEALING TO SOLVE ROUTING AND LOCATION-PROBLEMS [J].

GOLDEN, BL ;

SKISCIM, CC .

NAVAL RESEARCH LOGISTICS, 1986, 33 (02) :261-279

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

Hochbaum, DS ;

Landy, D .

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

← 1 2 3 →