Scheduling of uniform parallel machines with s-precedence constraints

被引：5

作者：

Kim, Eun-Seok ^{[1
]}

机构：

[1] City Univ London, Cass Business Sch, London EC1Y 8TZ, England

来源：

MATHEMATICAL AND COMPUTER MODELLING | 2011年 / 54卷 / 1-2期

关键词：

Uniform parallel machine scheduling; Precedence constraints; Weighted total completion time; Heuristic;

D O I：

10.1016/j.mcm.2011.03.001

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper considers a problem of scheduling s-precedence constrained jobs on machines in parallel which have different speeds. The objective is to minimize the weighted total completion time. The s-precedence relation between two jobs i and j represents the situation where job j is constrained from processing until job i starts processing, which is different from the standard definition of a precedence relation where j cannot start until i completes. An LP-based heuristic procedure is derived for the problem. Numerical experiments are conducted to show that the derived heuristic finds effective solutions. (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：576 / 583

页数：8

共 50 条

[31] SINGLE-MACHINE SCHEDULING POLYHEDRA WITH PRECEDENCE CONSTRAINTS [J].

QUEYRANNE, M ;

WANG, YG .

MATHEMATICS OF OPERATIONS RESEARCH, 1991, 16 (01) :1-20

[32] DSS approach for heterogeneous parallel machines scheduling considering proximate supply chain constraints [J].

Azzamouri, Ahiam ;

Bara, Najat ;

Elfirdoussi, Sclwa ;

Essaadi, Imane ;

Fontane, Frederic ;

Giard, Vincent .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2020, 58 (18) :5502-5520

[33] Mixed Integer Linear Programming for a Real-World Parallel Machine Scheduling Problem with Workforce and Precedence Constraints [J].

Caselli, Giulia ;

Delorme, Maxence ;

Iori, Manuel ;

Magni, Carlo Alberto .

OPTIMIZATION IN ARTIFICIAL INTELLIGENCE AND DATA SCIENCES, 2022, :61-71

[34] Efficient Approximation Algorithms for Scheduling Coflows With Precedence Constraints in Identical Parallel Networks to Minimize Weighted Completion Time [J].

Chen, Chi-Yeh .

IEEE TRANSACTIONS ON SERVICES COMPUTING, 2024, 17 (05) :2349-2364

[35] Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times [J].

Cao, Jianfa ;

Yuan, Jinjiang ;

Li, Wenjie ;

Bu, Hailin .

INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2011, 42 (01) :51-55

[36] Handling precedence constraints in scheduling problems by the sequence pair representation [J].

Kozik, Andrzej .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (02) :445-472

[37] Uniprocessor scheduling under precedence constraints for embedded systems design [J].

Mangeruca, Leonardo ;

Baleani, Massimo ;

Ferrari, Alberto ;

Sangiovanni-Vincentelli, Alberto .

ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2008, 7 (01)

[38] A heuristic approach for scheduling activities with 'OR'-precedence constraints at an underground mine [J].

Nancel-Penard, Pierre ;

Morales, Nelson ;

Rojas, Valentina ;

Gonzalez, Tomas .

INTERNATIONAL JOURNAL OF MINING RECLAMATION AND ENVIRONMENT, 2020, 34 (10) :748-762

[39] A new formulation for scheduling unrelated processor under precedence constraints [J].

Maculan, N ;

Porto, SCS ;

Ribeiro, CC ;

de Souza, CC .

RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1999, 33 (01) :87-92

[40] On the approximability of average completion time scheduling under precedence constraints [J].

Woeginger, GJ .

DISCRETE APPLIED MATHEMATICS, 2003, 131 (01) :237-252

← 1 2 3 4 5 →