This study evaluates various Mixed Integer Programming (MIP) formulations for solving single-machine and parallel-machine scheduling problems, with the objective of minimizing the total completion time and the makespan of jobs. Through extensive numerical study, the MIP formulation, which is suitable for dealing with each specific single-machine or parallel-machine scheduling problem, is identified. Benchmarks are also provided for the development of other algorithms for future research.

Introduction

The single-machine scheduling problem (SMSP), which is one of the most studied issues relating to manufacturing systems, can be found in numerous real-world production systems that require the effective scheduling of jobs performed on a unique machine. In the past several decades, a wide variety of studies have focused on SMSPs, in order to consider different scheduling criteria and explore efficient and effective methods to find optimal and near-optimal schedules [1], [2]. As a generalization of the SMSP, the parallel-machine scheduling problem (PMSP) has also received considerable attention from researchers [3], [4]. According to the similarity of the machines used for processing, PMSP issues can be further classified as identical PMSPs (IPMSPs), non-identical PMSPs (NIPMSPs), and unrelated PMSPs (UPMSPs). In recent years, many PMSP-related studies have endeavored to develop efficient heuristics (e.g., [5] and [6]). For many NP-hard problems, Mixed Integer Programming (MIP) is one of the exact methods commonly used to find optimal solutions for small- and medium-sized problems, as well as lower and/or upper bounds in larger problems, and to benchmark the quality of the solutions and efficiency of the compared methods [7]–[۹]. The advantages of using MIP rather than other approaches (e.g. heuristics and metaheuristics) for solving small- to medium-size NP-hard problems include but are not limited to the following. First, MIP is a common language that uniquely describes a problem in strictly mathematical terms. Second, there are many types of commercially available software that can be used to solve such problems out-of-the-box without further knowledge in scheduling or coding from the user.