Title: An improved MIP-based approach to minimise total earliness and tardiness in unrelated parallel machines scheduling with machine idle time

Authors: Chi-Yang Tsai; Yi-Chen Wang

Addresses: Department of Industrial Engineering and Management, Yuan-Ze University, 135 Yuan-Tung Road, Chung-Li, 32003, Taiwan ' Department of Industrial Engineering and Management, Yuan-Ze University, 135 Yuan-Tung Road, Chung-Li, 32003, Taiwan

Abstract: This paper proposes an effective and efficient mixed integer linear programming (MIP) formulation of the unrelated parallel machine scheduling problem with the objective of minimising total earliness and tardiness (ET) and explores how scheduling performance can be improved by allowing machine idle time. In addition, four simple dispatching rules are utilised to improve solution efficiency. From the results of experiments, it is found that: 1) the improved MIP formulation fixes a potential problem of existing models in literature; 2) the ET value can be significantly reduced if machine idle time is properly allowed before jobs; 3) the utilised dispatching rules yield comparable efficient and quality solutions.

Keywords: parallel machine scheduling; unrelated parallel machines; machine idle time; total earliness; total tardiness; mixed integer programming; MIP; dispatching rules; scheduling performance.

DOI: 10.1504/IJMTM.2015.071220

International Journal of Manufacturing Technology and Management, 2015 Vol.29 No.5/6, pp.271 - 287

Received: 23 Dec 2014
Accepted: 04 Mar 2015
Published online: 17 Aug 2015 *

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