Iterative Simulation and Optimization approach for job shop scheduling

Ketki Kulkarni; Jayendran Venkateswaran

doi:10.1109/WSC.2014.7020013

Iterative Simulation and Optimization approach for job shop scheduling

Ketki Kulkarni, Jayendran Venkateswaran

HUMLOG - The Humanitarian Logistics and Supply Chain Research Institute, Helsinki

Indian Institute of Technology Bombay

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

7 Citations (Scopus)

Abstract

In this paper, we present an iterative scheme integrating simulation with an optimization model, for solving complex problems, viz., job shop scheduling. The classical job shop scheduling problem which is NP-Hard, has often been modelled as Mixed-Integer Programming (MIP) model and solved using exact algorithms (for example, branch-and-bound and branch-and-cut) or using meta-heuristics (for example, Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing). In the proposed Iterative Simulation-Optimization (ISO) approach, we use a modified formulation of the scheduling problem where the operational aspects of the job shop are captured only in the simulation model. Two new decision variables, controller delays and queue priorities are used to introduce feedback constraints, that help exchange information between the two models. The proposed method is tested using benchmark instances from the OR library. The results indicate that the method gives near optimal schedules in a reasonable computational time.

Original language	English
Title of host publication	Proceedings of the 2014 Winter Simulation Conference, WSC 2014
Editors	Andreas Tolk, Levent Yilmaz, Saikou Y. Diallo, Ilya O. Ryzhov
Number of pages	12
Publisher	Institute of Electrical and Electronics Engineers Inc.
Publication date	23.01.2015
Pages	1620-1631
Article number	7020013
ISBN (Electronic)	978-1-4799-7486-3
DOIs	https://doi.org/10.1109/WSC.2014.7020013
Publication status	Published - 23.01.2015
MoE publication type	A4 Article in conference proceedings
Event	2014 Winter Simulation Conference, WSC 2014 - Savannah, United States Duration: 07.12.2014 → 10.12.2014

Publication series

Name	Proceedings - Winter Simulation Conference
Volume	2015-January
ISSN (Print)	0891-7736

Keywords

214 Mechanical engineering
Analytical models
Computational modeling
Mathematical model
Optimization
Job shop scheduling
Schedules
Linear programming

Access to Document

10.1109/WSC.2014.7020013

OpenUrl availability

Full text

Cite this

Kulkarni, K., & Venkateswaran, J. (2015). Iterative Simulation and Optimization approach for job shop scheduling. In A. Tolk, L. Yilmaz, S. Y. Diallo, & I. O. Ryzhov (Eds.), Proceedings of the 2014 Winter Simulation Conference, WSC 2014 (pp. 1620-1631). Article 7020013 (Proceedings - Winter Simulation Conference; Vol. 2015-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/WSC.2014.7020013

Kulkarni, Ketki ; Venkateswaran, Jayendran. / Iterative Simulation and Optimization approach for job shop scheduling. Proceedings of the 2014 Winter Simulation Conference, WSC 2014. editor / Andreas Tolk ; Levent Yilmaz ; Saikou Y. Diallo ; Ilya O. Ryzhov. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 1620-1631 (Proceedings - Winter Simulation Conference).

@inproceedings{1c2aa23c5b794a438ea9cf108be2321f,

title = "Iterative Simulation and Optimization approach for job shop scheduling",

abstract = "In this paper, we present an iterative scheme integrating simulation with an optimization model, for solving complex problems, viz., job shop scheduling. The classical job shop scheduling problem which is NP-Hard, has often been modelled as Mixed-Integer Programming (MIP) model and solved using exact algorithms (for example, branch-and-bound and branch-and-cut) or using meta-heuristics (for example, Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing). In the proposed Iterative Simulation-Optimization (ISO) approach, we use a modified formulation of the scheduling problem where the operational aspects of the job shop are captured only in the simulation model. Two new decision variables, controller delays and queue priorities are used to introduce feedback constraints, that help exchange information between the two models. The proposed method is tested using benchmark instances from the OR library. The results indicate that the method gives near optimal schedules in a reasonable computational time.",

keywords = "214 Mechanical engineering, Analytical models, Computational modeling, Mathematical model, Optimization, Job shop scheduling, Schedules, Linear programming",

author = "Ketki Kulkarni and Jayendran Venkateswaran",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 Winter Simulation Conference, WSC 2014 ; Conference date: 07-12-2014 Through 10-12-2014",

year = "2015",

month = jan,

day = "23",

doi = "10.1109/WSC.2014.7020013",

language = "English",

series = "Proceedings - Winter Simulation Conference",

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

pages = "1620--1631",

editor = "Andreas Tolk and Levent Yilmaz and Diallo, {Saikou Y.} and Ryzhov, {Ilya O.}",

booktitle = "Proceedings of the 2014 Winter Simulation Conference, WSC 2014",

}

Kulkarni, K & Venkateswaran, J 2015, Iterative Simulation and Optimization approach for job shop scheduling. in A Tolk, L Yilmaz, SY Diallo & IO Ryzhov (eds), Proceedings of the 2014 Winter Simulation Conference, WSC 2014., 7020013, Proceedings - Winter Simulation Conference, vol. 2015-January, Institute of Electrical and Electronics Engineers Inc., pp. 1620-1631, 2014 Winter Simulation Conference, WSC 2014, Savannah, United States, 07.12.2014. https://doi.org/10.1109/WSC.2014.7020013

Iterative Simulation and Optimization approach for job shop scheduling. / Kulkarni, Ketki; Venkateswaran, Jayendran.
Proceedings of the 2014 Winter Simulation Conference, WSC 2014. ed. / Andreas Tolk; Levent Yilmaz; Saikou Y. Diallo; Ilya O. Ryzhov. Institute of Electrical and Electronics Engineers Inc., 2015. p. 1620-1631 7020013 (Proceedings - Winter Simulation Conference; Vol. 2015-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Iterative Simulation and Optimization approach for job shop scheduling

AU - Kulkarni, Ketki

AU - Venkateswaran, Jayendran

PY - 2015/1/23

Y1 - 2015/1/23

N2 - In this paper, we present an iterative scheme integrating simulation with an optimization model, for solving complex problems, viz., job shop scheduling. The classical job shop scheduling problem which is NP-Hard, has often been modelled as Mixed-Integer Programming (MIP) model and solved using exact algorithms (for example, branch-and-bound and branch-and-cut) or using meta-heuristics (for example, Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing). In the proposed Iterative Simulation-Optimization (ISO) approach, we use a modified formulation of the scheduling problem where the operational aspects of the job shop are captured only in the simulation model. Two new decision variables, controller delays and queue priorities are used to introduce feedback constraints, that help exchange information between the two models. The proposed method is tested using benchmark instances from the OR library. The results indicate that the method gives near optimal schedules in a reasonable computational time.

AB - In this paper, we present an iterative scheme integrating simulation with an optimization model, for solving complex problems, viz., job shop scheduling. The classical job shop scheduling problem which is NP-Hard, has often been modelled as Mixed-Integer Programming (MIP) model and solved using exact algorithms (for example, branch-and-bound and branch-and-cut) or using meta-heuristics (for example, Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing). In the proposed Iterative Simulation-Optimization (ISO) approach, we use a modified formulation of the scheduling problem where the operational aspects of the job shop are captured only in the simulation model. Two new decision variables, controller delays and queue priorities are used to introduce feedback constraints, that help exchange information between the two models. The proposed method is tested using benchmark instances from the OR library. The results indicate that the method gives near optimal schedules in a reasonable computational time.

KW - 214 Mechanical engineering

KW - Analytical models

KW - Computational modeling

KW - Mathematical model

KW - Optimization

KW - Job shop scheduling

KW - Schedules

KW - Linear programming

UR - http://www.scopus.com/inward/record.url?scp=84940532792&partnerID=8YFLogxK

U2 - 10.1109/WSC.2014.7020013

DO - 10.1109/WSC.2014.7020013

M3 - Conference contribution

AN - SCOPUS:84940532792

T3 - Proceedings - Winter Simulation Conference

SP - 1620

EP - 1631

BT - Proceedings of the 2014 Winter Simulation Conference, WSC 2014

A2 - Tolk, Andreas

A2 - Yilmaz, Levent

A2 - Diallo, Saikou Y.

A2 - Ryzhov, Ilya O.

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 Winter Simulation Conference, WSC 2014

Y2 - 7 December 2014 through 10 December 2014

ER -

Kulkarni K, Venkateswaran J. Iterative Simulation and Optimization approach for job shop scheduling. In Tolk A, Yilmaz L, Diallo SY, Ryzhov IO, editors, Proceedings of the 2014 Winter Simulation Conference, WSC 2014. Institute of Electrical and Electronics Engineers Inc. 2015. p. 1620-1631. 7020013. (Proceedings - Winter Simulation Conference). doi: 10.1109/WSC.2014.7020013

Iterative Simulation and Optimization approach for job shop scheduling

Abstract

Publication series

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this