A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

被引：2

作者：

Nessah, Rabia ^{[1
]}

Yalaoui, Farouk ^{[1
]}

Chu, Chengbin ^{[1
]}

机构：

[1] Univ Technol Troyes, Inst Charles Delaunay, OSI, CNRS FRE 28248, F-10010 Troyes, France

来源：

2006 INTERNATIONAL CONFERENCE ON SERVICE SYSTEMS AND SERVICE MANAGEMENT, VOLS 1 AND 2, PROCEEDINGS | 2006年

关键词：

identical parallel machine; scheduling; release dates; lower bound; dominance properties; branch and bound;

D O I：

10.1109/ICSSSM.2006.320678

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

In this paper, we consider an identical parallel machine scheduling problem with release dates. The objective is to minimize the total weighted completion time. This problem is know to be strongly NP-hard. We propose two lower bounds. We present an efficient heuristic, we also propose some dominance properties. A branch and bound algorithm in which the heuristic, the lower bounds and the dominance properties are incorporated is proposed and tested on a large set of randomly generated instances.

引用

页码：1192 / 1198

页数：7

共 50 条

[31] A flowshop scheduling algorithm to minimize total weighted completion time
Zhao, CL
Zhang, QL
Tang, HY
PROCEEDINGS OF THE 4TH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION, VOLS 1-4, 2002, : 1485 - 1488
[32] A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property
Shim, Sang-Oh
Kim, Yeong-Dae
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (03) : 863 - 875
[33] Scheduling open shops with parallel machines to minimize total completion time
Naderi, B.
Ghomi, S. M. T. Fatemi
Aminnayeri, M.
Zandieh, M.
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2011, 235 (05) : 1275 - 1287
[34] Scheduling identical parallel machines to minimize total tardiness
Biskup, Dirk
Herrmann, Jan
Gupta, Jatinder N. D.
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2008, 115 (01) : 134 - 142
[35] Scheduling on parallel identical machines to minimize total tardiness
Shim, Sang-Oh
Kim, Yeong-Dae
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 177 (01) : 135 - 146
[36] A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint
Lee, Ju-Yong
Kim, Yeong-Dae
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2015, 66 (09) : 1542 - 1554
[37] Branch and bound algorithms for single-machine scheduling with batch set-up times to minimize total weighted completion time
Crauwels, HAJ
Hariri, AMA
Potts, CN
Van Wassenhove, LN
ANNALS OF OPERATIONS RESEARCH, 1998, 83 (0) : 59 - 76
[38] A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates
Baptiste, P
Carlier, J
Jouglet, A
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 158 (03) : 595 - 608
[39] Scheduling unrelated parallel machines to minimize total weighted tardiness
Liaw, CF
Lin, YK
Cheng, CY
Chen, MC
COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (12) : 1777 - 1789
[40] Parallel Identical Machines Scheduling to Minimize the Maximum Inter-completion Time with Uncertain Processing Time
Sui, Yang
Wang, Zhaojie
IFAC PAPERSONLINE, 2022, 55 (10): : 2599 - 2604

← 1 2 3 4 5 →