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 条

[21] Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints
Su, Ling-Huey
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 40 (5-6): : 572 - 581
[22] Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints
Ling-Huey Su
The International Journal of Advanced Manufacturing Technology, 2009, 40 : 572 - 581
[23] Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates
Nessah, Rabia
Kacem, Imed
COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (03) : 471 - 478
[24] Online bounded-batch scheduling to minimize total weighted completion time on parallel machines
Ma, Ran
Wan, Long
Wei, Lijun
Yuan, Jinjiang
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2014, 156 : 31 - 38
[25] A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan
Ozturk, Onur
Begen, Mehmet A.
Zaric, Gregory S.
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2017, 55 (06) : 1815 - 1831
[26] On the minimization of total weighted flow time with identical and uniform parallel machines
Azizoglu, M
Kirca, O
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 113 (01) : 91 - 100
[27] Online Scheduling with Rejection to Minimize the Total Weighted Completion Time Plus the Total Rejection Cost on Parallel Machines
Ma R.
Yuan J.-J.
Journal of the Operations Research Society of China, 2016, 4 (1) : 111 - 119
[28] Serial batch scheduling on uniform parallel machines to minimize total completion time
Li, Song-Song
Zhang, Yu-Zhong
INFORMATION PROCESSING LETTERS, 2014, 114 (12) : 692 - 695
[29] A branch and bound algorithm to minimize total weighted tardiness on a single processor
Babu, P
Peridy, L
Pinson, E
ANNALS OF OPERATIONS RESEARCH, 2004, 129 (1-4) : 33 - 46
[30] A Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor
Pascal Babu
Laurent Peridy
Eric Pinson
Annals of Operations Research, 2004, 129 : 33 - 46

← 1 2 3 4 5 →