problem-independent search heuristic for single machine scheduling with release dates and deadlines

被引：1

作者：

Laalaoui, Yacine ^{[1
]}

M'Hallah, Rym ^{[2
]}

机构：

[1] Taif Univ, Dept Informat Technol, Taif, Saudi Arabia

[2] Kings Coll London, Dept Engn, London, England

来源：

2022 IEEE SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE (SSCI) | 2022年

关键词：

Scheduling; Search heuristic; Release dates; Deadlines; Position manipulation; BACKTRACKING; TARDINESS; EARLINESS;

D O I：

10.1109/SSCI51031.2022.10022172

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper presents a new search heuristic F that determines the feasibility of scheduling a set of jobs on a single machine where each job is characterized by its release date, processing time, and deadline. F alternates between (i) a construction phase that builds a partial feasible solution by assigning positions to on-time jobs and (ii) a backtracking phase that removes on-time jobs that are causing the tardiness of the current job. F chooses jobs according to a new dynamic priority rule. It stops when it successfully schedules all jobs or when it reaches a threshold runtime. F is unique in two ways. It does not guide its search via a problem-dependent heuristic. In addition, its parameters are problem-independent; thus, require no tuning. Experimental results provide computational evidence that F is superior to existing heuristics such as NEH and Profile Fitting.

引用

页码：782 / 789

页数：8

共 18 条

[1] Supply chain scheduling: Sequence coordination [J].

Agnetis, Alessandro ;

Hall, Nicholas G. ;

Pacciarelli, Dario .

DISCRETE APPLIED MATHEMATICS, 2006, 154 (15) :2044-2063

[2] Conflict-directed backjumping revisited [J].

Chen, XQ ;

van Beek, P .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2001, 14 :53-81

[3] Backjump-based backtracking for constraint satisfaction problems [J].

Dechter, R ;

Frost, D .

ARTIFICIAL INTELLIGENCE, 2002, 136 (02) :147-188

[4] Resource-constrained project scheduling: a heuristic for the multi-mode case [J].

Heilmann, R .

OR SPEKTRUM, 2001, 23 (03) :335-357

[5] Squeaky wheel optimization [J].

Joslin, DE ;

Clements, DP .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 1999, 10 :353-373

[6] Pre-run-time scheduling in real-time systems: Current researches and Artificial Intelligence perspectives [J].

Laalaoui, Yacine ;

Bouguila, Nizar .

EXPERT SYSTEMS WITH APPLICATIONS, 2014, 41 (05) :2196-2210

[7] Learning and backtracking in non-preemptive scheduling of tasks under timing constraints [J].

Laalaoui, Yacine ;

Drias, Habiba .

SOFT COMPUTING, 2011, 15 (06) :1071-1086

[8] Ant Colony System with Stagnation Avoidance For the Scheduling of Real-Time Tasks [J].

Laalaoui, Yacine ;

Drias, Habiba ;

Bouridah, Adel ;

Ahmed, R. B. .

2009 IEEE SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE IN SCHEDULING: (CI-SCHED), 2009, :1-6

[9] Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling [J].

Lang, Fabian ;

Fink, Andreas ;

Brandt, Tobias .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 248 (01) :192-203

[10] Reasoning from last conflict(s) in constraint programming [J].

Lecoutre, Christophe ;

Sais, Lakhdar ;

Tabary, Sebastien ;

Vidal, Vincent .

ARTIFICIAL INTELLIGENCE, 2009, 173 (18) :1592-1614

← 1 2 →