An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints

被引：89

作者：

Sadfi, C

Penz, B

Rapine, C

Blazewicz, J

Formanowicz, P

机构：

[1] Lab GILCO, F-38031 Grenoble 1, France

[2] Poznan Univ Tech, Inst Comp Sci, PL-60965 Poznan, Poland

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2005年 / 161卷 / 01期

关键词：

single machine scheduling; total completion time; availability constraints; approximation algorithm; worst case analysis;

D O I：

10.1016/j.ejor.2003.08.026

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we study the single machine total completion scheduling problem subject to a period of maintenance. We propose an approximation algorithm to solve the problem with a worst case error bound of 3/17. Furthermore, an example is provided to show that the bound is tight. Computational experiments and an analysis are given afterwards. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：3 / 10

页数：8

共 50 条

[1] Minimising the total completion time in a single machine scheduling problem under bimodal flexible periodic availability constraints
Mashkani, O.
Moslehi, G.
INTERNATIONAL JOURNAL OF COMPUTER INTEGRATED MANUFACTURING, 2016, 29 (03) : 323 - 341
[2] Total weighted completion scheduling problem with availability constraints
Sadfi, Cherif
Kacem, Imed
Liu, Wei
CIE: 2009 INTERNATIONAL CONFERENCE ON COMPUTERS AND INDUSTRIAL ENGINEERING, VOLS 1-3, 2009, : 134 - +
[3] Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints
Huo, Yumei
Zhao, Hairong
THEORETICAL COMPUTER SCIENCE, 2011, 412 (12-14) : 1081 - 1091
[4] Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time
Chen, Yong
Zhang, An
Tan, Zhiyi
INFORMATION SCIENCES, 2013, 251 : 150 - 163
[5] Genetic Local Search Algorithm for minimizing the total completion time in single machine scheduling problem with release dates and precedence constraints
Zaidi, Ichraf
Mrad, Mehdi
Ladhari, Talel
2013 5TH INTERNATIONAL CONFERENCE ON MODELING, SIMULATION AND APPLIED OPTIMIZATION (ICMSAO), 2013,
[6] A Single Machine Scheduling Problem Considering Machine Availability Constraints
Wang J.
Chen L.
Yang W.
Shanghai Jiaotong Daxue Xuebao/Journal of Shanghai Jiaotong University, 2021, 55 (01): : 103 - 110
[7] An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time
Pan, YP
OPERATIONS RESEARCH LETTERS, 2003, 31 (06) : 492 - 496
[8] Lower bounds for total weighted completion scheduling problem with availability constraints
Sadfi, Cherif
Kacem, Imed
Liu, Wei
CIE: 2009 INTERNATIONAL CONFERENCE ON COMPUTERS AND INDUSTRIAL ENGINEERING, VOLS 1-3, 2009, : 159 - 163
[9] Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints
Vahedi-Nouri, Behdin
Fattahi, Parviz
Rohaninejad, Mohammad
Tavakkoli-Moghaddam, Reza
APPLIED MATHEMATICAL MODELLING, 2013, 37 (05) : 3126 - 3137
[10] An iterative heuristic for the single machine dynamic total completion time scheduling problem
Chand, S
Traub, R
Uzsoy, R
COMPUTERS & OPERATIONS RESEARCH, 1996, 23 (07) : 641 - 651

← 1 2 3 4 5 →