Title: Single machine scheduling problem of minimising weighted sum of maximum weighted earliness and weighted number of tardy jobs
Authors: Parvaneh Eghbalpor; Mohammad Reisi-Nafchi; Ghasem Moslehi
Addresses: Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156-83111, Iran ' Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156-83111, Iran ' Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156-83111, Iran
Abstract: Due to the intense competition in the markets, manufacturers are trying to deliver their customers' orders in a timely manner. Therefore, taking into account just-in-time production criteria in scheduling problems is of great importance. In this article, two criteria of maximum weighted earliness and weighted number of tardy jobs are simultaneously considered in a single machine environment for the first time. An optimal algorithm is proposed to minimise maximum weighted earliness in a single machine scheduling. Then a mixed integer programming model is presented for the bi-criteria problem. In addition, a branch-and-bound, with upper and lower bounds and dominance rules are presented to optimally solve the bi-criteria problem. To evaluate the performance of proposed methods a set of instances was generated and solved. The computational results showed that the mixed integer programming model and the branch-and-bound were capable of solving instances up to 26 and 34 jobs in size, respectively. [Submitted 1 November 2018; Accepted 1 September 2019]
Keywords: scheduling; weighted maximum earliness; weighted number of tardy jobs; single machine; branch-and-bound; mixed integer programming.
International Journal of Manufacturing Research, 2021 Vol.16 No.2, pp.154 - 186
Received: 01 Nov 2018
Accepted: 01 Sep 2019
Published online: 09 Jun 2021 *