Comparative Analysis of Mixed Integer Programming Formulations for Single-Machine and Parallel-Machine Scheduling Problems

Kuo Ching Ying; Chen Yang Cheng; Shih Wei Lin; Chia Yang Hung

doi:10.1109/ACCESS.2019.2947685

Comparative Analysis of Mixed Integer Programming Formulations for Single-Machine and Parallel-Machine Scheduling Problems

Kuo Ching Ying
, Chen Yang Cheng
, Shih Wei Lin^*
, Chia Yang Hung

^*Corresponding author for this work

National Taipei University of Technology
Chang Gung University
Chang Gung Memorial Hospital
Ming Chi University of Technology
United Microelectronics Corporation

Research output: Contribution to journal › Journal Article › peer-review

9 Scopus citations

Abstract

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.

Original language	English
Article number	8882214
Pages (from-to)	152998-153011
Number of pages	14
Journal	IEEE Access
Volume	7
DOIs	https://doi.org/10.1109/ACCESS.2019.2947685
State	Published - 2019
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2013 IEEE.

Keywords

Scheduling
makespan
parallel-machine
single-machine
total completion time

Access to Document

10.1109/ACCESS.2019.2947685

Cite this

@article{72fd37bc3cee4726a58203a93e0314a0,

title = "Comparative Analysis of Mixed Integer Programming Formulations for Single-Machine and Parallel-Machine Scheduling Problems",

abstract = "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.",

keywords = "Scheduling, makespan, parallel-machine, single-machine, total completion time",

author = "Ying, \{Kuo Ching\} and Cheng, \{Chen Yang\} and Lin, \{Shih Wei\} and Hung, \{Chia Yang\}",

note = "Publisher Copyright: {\textcopyright} 2013 IEEE.",

year = "2019",

doi = "10.1109/ACCESS.2019.2947685",

language = "英语",

volume = "7",

pages = "152998--153011",

journal = "IEEE Access",

issn = "2169-3536",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Comparative Analysis of Mixed Integer Programming Formulations for Single-Machine and Parallel-Machine Scheduling Problems

AU - Ying, Kuo Ching

AU - Cheng, Chen Yang

AU - Lin, Shih Wei

AU - Hung, Chia Yang

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Scheduling

KW - makespan

KW - parallel-machine

KW - single-machine

KW - total completion time

UR - https://www.scopus.com/pages/publications/85078327927

U2 - 10.1109/ACCESS.2019.2947685

DO - 10.1109/ACCESS.2019.2947685

M3 - 文章

AN - SCOPUS:85078327927

SN - 2169-3536

VL - 7

SP - 152998

EP - 153011

JO - IEEE Access

JF - IEEE Access

M1 - 8882214

ER -

Comparative Analysis of Mixed Integer Programming Formulations for Single-Machine and Parallel-Machine Scheduling Problems

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this