Sequencing single machine multiple-class customer order jobs using heuristics and improved simulated annealing algorithms

¹ Department of Statistics, Feng Chia University, Taichung 40724, Taiwan
² College of Mathematics Science, Chongqing Normal University, 401331 Chongqing, P.R. China
³ SolBridge International School of Business, Woosong University, Daejeon 34613, Republic of Korea
⁴ Department of E-sport Technology Management, Cheng Shiu University, Kaohsiung City 83347, Taiwan
⁵ Université de Tunis, Institut supérieur de gestion de Tunis, SMART Lab., Tunis, Tunisia

^* Corresponding author: cchwu@fcu.edu.tw

Received: 2 August 2022
Accepted: 13 April 2023

Abstract

The multiple job class scheduling problem arises in contexts where a group of jobs belong to multiple classes and in which if all jobs in the same class are operated together, extra setup times would not be needed. On the other hand, the customer order scheduling problem focuses on finishing all jobs from the same order at the same time in order to reduce shipping costs. However, works on customer orders coupled with class setup times do not appear often in the literature. Hence we address here a bicriteria single machine customer order scheduling problem together with multiple job classes. The optimality criterion minimizes a linear combination of the sum of the ranges and sum of tardiness of all customer orders. In light of the high complexity of the concerned problem, we propose a lower bound formula and a property to be used in a branch-and-bound method for optimal solutions. To find approximate solutions, we then propose four heuristics together with a local search method, four cloudy theoretical simulated annealing and a cloudy theoretical simulated annealing hyperheuristic along with five low-level heuristics. The simulation results of the proposed heuristics and algorithms are analyzed.