Novel Hybrid Algorithms for a Single Machine Scheduling Problem With an Overtime Constraint

Novel Hybrid Algorithms for a Single Machine Scheduling Problem With an Overtime Constraint

Jakkrit Latthawanichphan, Watcharapan Sukkerd, Watchara Songserm, Teeradej Wuttipornpun
Copyright: © 2022 |Pages: 26
DOI: 10.4018/IJKSS.298708
Article PDF Download
Open access articles are freely available for download

Abstract

In this paper, a single machine scheduling problem with an overtime constraint is studied. The objective is to minimise the total penalty cost defined as the sum of tardy, early, and overtime costs. Three novel hybrid algorithms that hybridise a new heuristic with genetic algorithm, tabu search, and simulated annealing, referred to as GAH, TSH, and SAH, are proposed to solve the problem. In each iteration of the proposed hybrid algorithms, a given metaheuristic is used to determine a sequence of jobs, whereas a new heuristic is used to minimise the total penalty cost of the sequence using a backward-forward scheduling technique and a penalty cost trade-off process. Exhaustive experiments are conducted to evaluate the effectiveness of the proposed hybrid algorithms. For medium-scale and large-scale problems, TSH with its best common parameter setting referred to as TSH2, clearly outperforms the exact algorithm, whereas both algorithms can obtain the optimal solution for small-scale problems. In addition, the computational time of TSH2 is in an acceptable range for the planner.
Article Preview
Top

2. Literature Review

Although, the one-stage or single machine (SM) problem is the simplest combinatorial scheduling problem, it is generally categorised as NP-hard when dealing with large-scale sophisticated problems (Du & Leung, 1990; Jaramillo & Erkoc, 2017; Vakhania, 2018; Yang et al., 2004; Zhu & You, 2017). The objectives always studied in the literature are: tardiness, earliness, lateness, overtime, setup time, flow time, makespan, and their variants. In terms of time, each of them is commonly referred to as “penalty time.” And, in terms of cost, it is referred to as “penalty cost.”

Complete Article List

Search this Journal:
Reset
Volume 15: 1 Issue (2024)
Volume 14: 1 Issue (2023)
Volume 13: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing