Title: Scheduling the capacitated identical parallel machines problem: a new formulation with sequence-dependent setup costs and different due dates

Authors: Majid Esmaelian; Ahmad Sobhani; Hadi Shahmoradi; Milad Mohammadi

Addresses: Department of Management, University of Isfahan, Hezarjerib St., Azadi Square, Isfahan, Iran ' Department of Decision and Information Sciences, School of Business Administration, Oakland University, Rochester, Michigan, USA ' Department of Management, University of Isfahan, Hezarjerib St., Azadi Square, Isfahan, Iran ' Department of Management, University of Isfahan, Hezarjerib St., Azadi Square, Isfahan, Iran

Abstract: This paper schedules capacitated parallel machines of a real production system by considering different quantities of production and processing times required to complete customer orders. A new mixed linear programming model is developed according to the concept of constrained vehicle routing problems to have a complete schedule for machines by determining the sequence of both jobs and idle times for each machine. The optimisation model minimises the total cost of the production system, including tardiness, earliness and sequence-dependent setup costs. A constraint programming (CP) model and a meta-heuristic hybrid algorithm are also developed to compare their results with the mixed linear programming model. The numerical findings show that the total cost estimated by the mixed integer programming model is 10%-13% better (lower) than the ones estimated by the CP model and the meta-heuristic algorithm when small instances of the scheduling problem are solved. By increasing the size of the scheduling problem, the meta-heuristic algorithm shows the best computational performance estimating 11% better (lower) total cost compared with the CP model. [Received: 14 April 2020; Accepted: 26 October 2020]

Keywords: capacitated identical parallel machines; constrained vehicle routing problem; mixed integer linear programming; constraint programming; meta-heuristic algorithm.

DOI: 10.1504/EJIE.2021.117337

European Journal of Industrial Engineering, 2021 Vol.15 No.5, pp.643 - 674

Received: 14 Apr 2020
Accepted: 26 Oct 2020
Published online: 31 Aug 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article