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

Jakkrit Latthawanichphan, Watcharapan Sukkerd, Watchara Songserm and Teeradej Wuttipornpun
Additional contact information
Jakkrit Latthawanichphan: King Mongkut's University of Technology North Bangkok, Thailand
Watcharapan Sukkerd: Rajamangala University of Technology Phra Nakhon, Thailand
Watchara Songserm: Rajamangala University of Technology Phra Nakhon, Thailand
Teeradej Wuttipornpun: King Mongkut's University of Technology North Bangkok, Thailand

International Journal of Knowledge and Systems Science (IJKSS), 2022, vol. 13, issue 1, 1-26

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.

Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve.aspx?doi=10.4018/IJKSS.298708 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jkss00:v:13:y:2022:i:1:p:1-26

Access Statistics for this article

International Journal of Knowledge and Systems Science (IJKSS) is currently edited by Van Nam Huynh

More articles in International Journal of Knowledge and Systems Science (IJKSS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().