Exact resolution of the one-machine sequencing problem with no machine idle time

被引：19

作者：

Carlier, Jacques ^{[1
]}

Hermes, Fatma ^{[2
]}

Moukrim, Aziz ^{[1
]}

Ghedira, Khaled ^{[3
]}

机构：

[1] Univ Technol Compiegne, Ctr Rech Royallieu, F-60205 Compiegne, France

[2] Fac Sci Math Phys & Nat Tunis, Tunis 1060, Tunisia

[3] Inst Super Gest Tunis, Bouchoucha 2000, Bardo, Tunisia

来源：

COMPUTERS & INDUSTRIAL ENGINEERING | 2010年 / 59卷 / 02期

关键词：

One-machine sequencing problem; No-idle constraint; Makespan; Release dates; Delivery times; EARLY/TARDY SCHEDULING PROBLEM; RELEASE DATES; DUE-DATES; HEURISTICS;

D O I：

10.1016/j.cie.2010.03.007

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper investigates the one-machine sequencing problem in a workshop where the machine has to satisfy the no-idle constraint, that is, the machine must process jobs without interruption. The objective is to minimize the makespan. Each job has a release date for which it is available for processing on the machine and a delivery time during which it must remain in the system after being processed by the machine. This problem has been studied without adding the no-idle constraint. It is solved in polynomial time, when the preemption of jobs is allowed, applying Jackson's rule. But, when the preemption of jobs is not allowed, it becomes strongly NP-hard. Although, it can be solved in a very short time using Carlier's branch and bound algorithm. Below, we propose to adapt Carlier's branch and bound method in order to calculate an optimal nonpreemptive schedule for the problem when adding the no-idle constraint. (c) 2010 Elsevier Ltd. All rights reserved.

引用

页码：193 / 199

页数：7

共 23 条

[1]

[Anonymous], 2005, ACM Sigact News, DOI DOI 10.1145/1067309.1067324

[2] SEQUENCING WITH DUE-DATES AND EARLY START TIMES TO MINIMIZE MAXIMUM TARDINESS [J].

BAKER, KR ;

SU, ZS .

NAVAL RESEARCH LOGISTICS, 1974, 21 (01) :171-176

[3] Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management [J].

Baptiste, Philippe .

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, :364-367

[4] SEQUENCING WITH EARLIEST STARTS AND DUE DATES WITH APPLICATION TO COMPUTING BOUNDS FOR (N/M/G/FMAX) PROBLEM [J].

BRATLEY, P ;

FLORIAN, M ;

ROBILLARD, P .

NAVAL RESEARCH LOGISTICS, 1973, 20 (01) :57-67

[5]

Brucker P., 1995, Scheduling Algorithms

[6] Jackson's Pseudo Preemptive Schedule for the Pm/ri, qi/Cmax scheduling problem [J].

Carlier, J ;

Pinson, E .

ANNALS OF OPERATIONS RESEARCH, 1998, 83 (0) :41-58

[7] THE ONE-MACHINE SEQUENCING PROBLEM [J].

CARLIER, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1982, 11 (01) :42-47

[8]

Carlier J., 1990, Annals of Operations Research, V26, P269

[9] On single-machine scheduling without intermediate delays [J].

Chretienne, Philippe .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (13) :2543-2550

[10]

Garey M., 1976, Computers and Intractability: A Guide to the Theory of NP-Completeness

← 1 2 3 →