An approximate/exact objective based search technique for solving general scheduling problems

Andrzej Kozik , Radosław Rudek


In this paper, we analyze single machine scheduling problems under the following minimization objectives: the maximum completion time (makespan), the total completion time and the maximum lateness, including fundamental practical aspects, which often occur in industrial or manufacturing reality: release dates, due dates, setup times, precedence constraints, deterioration (aging) of machines, as well as maintenance activities. To solve the problems, we propose an efficient representation of a solution and a fast neighborhood search technique, which calculates an approximation of criterion values in a constant time per solution in a neighborhood. On this basis, a novel approximate/exact search technique, using exact as well as approximate criterion values during search process, is introduced and used to develop efficient metaheuristic algorithms dedicated to the considered problems. Their efficiency is verified during computational experiments
Author Andrzej Kozik - [University of Opole (UO)]
Andrzej Kozik,,
- Uniwersytet Opolski
, Radosław Rudek (MISaF / IBI / DIT)
Radosław Rudek,,
- Department of Information Technologies
Journal seriesApplied Soft Computing, ISSN 1568-4946, (A 40 pkt)
Issue year2018
Publication size in sheets0.55
Keywords in EnglishScheduling, Precedence constraints, Setup time, Maintenance activity, Aging effect, Metaheuristic
ASJC Classification1712 Software
Languageen angielski
Kozik_Rudek_An_ approximate_exact_ objective_ based_ search2018.pdf 871 KB
Score (nominal)40
Score sourcejournalList
ScoreMinisterial score = 40.0, 05-02-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 2.369; WoS Impact Factor: 2018 = 4.873 (2) - 2018=4.858 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.