Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware

Jiachen Zhang; Giovanni Lo Bianco; J. Christopher Beck

doi:10.1609/icaps.v32i1.19826

Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware

Jiachen Zhang
, Giovanni Lo Bianco
, J. Christopher Beck

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

14 Citations (Scopus)

Abstract

The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm. © 2022, Association for the Advancement of Artificial Intelligence.

Original language	English
Title of host publication	Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022)
Editors	Akshat Kumar, Sylvie Thiébaux, Pradeep Varakantham, William Yeoh
Publisher	AAAI Press
Pages	404-412
Number of pages	9
Volume	32
ISBN (Print)	978-1-57735-874-9
DOIs	https://doi.org/10.1609/icaps.v32i1.19826
Publication status	Published - 2022
Externally published	Yes
Event	32nd International Conference on Automated Planning and Scheduling, ICAPS 2022 - Virtual, Online, Singapore Duration: 13 Jun 2022 → 24 Jun 2022

Publication series

Name	Proceedings International Conference on Automated Planning and Scheduling, ICAPS
Volume	32
ISSN (Print)	2334-0835
ISSN (Electronic)	2334-0843

Conference

Conference	32nd International Conference on Automated Planning and Scheduling, ICAPS 2022
Place	Singapore
City	Virtual, Online
Period	13/06/22 → 24/06/22

Funding

The authors would like to thank Fujitsu Limited and Fu-jitsu Consulting (Canada) Incorporated for providing financial support and access to the Digital Annealer at the University of Toronto. Partial funding for this work was provided by Fujitsu Limited and the Natural Sciences and Engineering Research Council of Canada.

Access Output

10.1609/icaps.v32i1.19826

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Zhang, J., Bianco, G. L., & Beck, J. C. (2022). Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware. In A. Kumar, S. Thiébaux, P. Varakantham, & W. Yeoh (Eds.), Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022) (Vol. 32, pp. 404-412). (Proceedings International Conference on Automated Planning and Scheduling, ICAPS; Vol. 32). AAAI Press. https://doi.org/10.1609/icaps.v32i1.19826

Zhang, Jiachen ; Bianco, Giovanni Lo ; Beck, J. Christopher. / Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware. Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022). editor / Akshat Kumar ; Sylvie Thiébaux ; Pradeep Varakantham ; William Yeoh. Vol. 32 AAAI Press, 2022. pp. 404-412 (Proceedings International Conference on Automated Planning and Scheduling, ICAPS).

@inproceedings{dbef6e30ece244638ee2e472934ec1b0,

title = "Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware",

abstract = "The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm. {\textcopyright} 2022, Association for the Advancement of Artificial Intelligence.",

author = "Jiachen Zhang and Bianco, \{Giovanni Lo\} and Beck, \{J. Christopher\}",

year = "2022",

doi = "10.1609/icaps.v32i1.19826",

language = "English",

isbn = "978-1-57735-874-9",

volume = "32",

series = "Proceedings International Conference on Automated Planning and Scheduling, ICAPS",

publisher = "AAAI Press",

pages = "404--412",

editor = "Akshat Kumar and Sylvie Thi{\'e}baux and Pradeep Varakantham and William Yeoh",

booktitle = "Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022)",

note = "32nd International Conference on Automated Planning and Scheduling, ICAPS 2022 ; Conference date: 13-06-2022 Through 24-06-2022",

}

Zhang, J, Bianco, GL & Beck, JC 2022, Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware. in A Kumar, S Thiébaux, P Varakantham & W Yeoh (eds), Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022). vol. 32, Proceedings International Conference on Automated Planning and Scheduling, ICAPS, vol. 32, AAAI Press, pp. 404-412, 32nd International Conference on Automated Planning and Scheduling, ICAPS 2022, Virtual, Online, Singapore, 13/06/22. https://doi.org/10.1609/icaps.v32i1.19826

Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware. / Zhang, Jiachen; Bianco, Giovanni Lo; Beck, J. Christopher.
Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022). ed. / Akshat Kumar; Sylvie Thiébaux; Pradeep Varakantham; William Yeoh. Vol. 32 AAAI Press, 2022. p. 404-412 (Proceedings International Conference on Automated Planning and Scheduling, ICAPS; Vol. 32).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware

AU - Zhang, Jiachen

AU - Bianco, Giovanni Lo

AU - Beck, J. Christopher

PY - 2022

Y1 - 2022

N2 - The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm. © 2022, Association for the Advancement of Artificial Intelligence.

AB - The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm. © 2022, Association for the Advancement of Artificial Intelligence.

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85142638797&origin=recordpage

U2 - 10.1609/icaps.v32i1.19826

DO - 10.1609/icaps.v32i1.19826

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-1-57735-874-9

VL - 32

T3 - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

SP - 404

EP - 412

BT - Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022)

A2 - Kumar, Akshat

A2 - Thiébaux, Sylvie

A2 - Varakantham, Pradeep

A2 - Yeoh, William

PB - AAAI Press

T2 - 32nd International Conference on Automated Planning and Scheduling, ICAPS 2022

Y2 - 13 June 2022 through 24 June 2022

ER -

Zhang J, Bianco GL, Beck JC. Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware. In Kumar A, Thiébaux S, Varakantham P, Yeoh W, editors, Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022). Vol. 32. AAAI Press. 2022. p. 404-412. (Proceedings International Conference on Automated Planning and Scheduling, ICAPS). Epub 2022 Jun 13. doi: 10.1609/icaps.v32i1.19826

Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware

Abstract

Publication series

Conference

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this