Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing

被引：151

作者：

Melouk, S ^{[1
]}

Damodaran, P

Chang, PY

机构：

[1] Texas A&M Univ, Dept Ind Engn, College Stn, TX 77843 USA

[2] SUNY Binghamton, Dept Syst Sci & Ind Engn, Binghamton, NY 13902 USA

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

来源：

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS | 2004年 / 87卷 / 02期

关键词：

simulated annealing; batch processing; scheduling;

D O I：

10.1016/S0925-5273(03)00092-6

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This research proposes a simulated annealing (SA) approach to minimize makespan for a single batch-processing machine. Each job has a corresponding processing time and size. The machine can process the jobs in batches as long as the machine capacity is not exceeded. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Random instances were generated to test our approach with respect to solution quality and run time. The results of the SA approach were compared to CPLEX. Our approach outperforms CPLEX on all the instances. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：141 / 147

页数：7

共 22 条

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

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

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

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

EGLESE, RW .

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

[5]

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

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

GOLDEN, BL ;

SKISCIM, CC .

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

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

Hochbaum, DS ;

Landy, D .

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

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

IKURA, Y ;

GIMPLE, M .

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

[9] OPTIMIZATION BY SIMULATED ANNEALING - AN EXPERIMENTAL EVALUATION .2. GRAPH-COLORING AND NUMBER PARTITIONING [J].

JOHNSON, DS ;

ARAGON, CR ;

MCGEOCH, LA ;

SCHEVON, C .

OPERATIONS RESEARCH, 1991, 39 (03) :378-406

[10] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680

← 1 2 3 →