A mixed integer linear programming modelling for the flexible cyclic jobshop problem

This paper addresses the Cyclic Jobshop Problem in a flexible context. The flexibility feature means that machines are able to perform several kinds of tasks. Hence, a solution of the scheduling problem does not only concern the starting times of the elementary tasks, but also the assignment of thes...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2020-02, Vol.285 (1-2), p.335-352
Main Authors: Quinton, Félix, Hamaz, Idir, Houssin, Laurent
Format: Article
Language:English
Subjects:
Benders decomposition
Business and Management
Combinatorics
Computer Science
Cycle time
Flexible assembly systems
Flexible manufacturing systems
Heuristic methods
Integer programming
Linear programming
Methods
Mixed integer
Operations Research
Operations Research/Decision Theory
Production scheduling
S.I.: Project Management and Scheduling 2018
Schedules
Scheduling (Management)
Task scheduling
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c501t-96c15bbfade207aa9114c0f051890af87298c27c3883fafe64e4f3947bbef6ee3
cites cdi_FETCH-LOGICAL-c501t-96c15bbfade207aa9114c0f051890af87298c27c3883fafe64e4f3947bbef6ee3
container_end_page 352
container_issue 1-2
container_start_page 335
container_title Annals of operations research
container_volume 285
creator Quinton, Félix
Hamaz, Idir
Houssin, Laurent
description This paper addresses the Cyclic Jobshop Problem in a flexible context. The flexibility feature means that machines are able to perform several kinds of tasks. Hence, a solution of the scheduling problem does not only concern the starting times of the elementary tasks, but also the assignment of these tasks to a unique machine. The objective considered in this paper is the minimisation of the cycle time of a periodic schedule. We formulate the problem as a Mixed Integer Linear Problem and propose a Benders decomposition method along with a heuristic procedure to speed up the solving of large instances. It consists in reducing the number of machines available for each task. Results of numerical experiments on randomly generated instances show that the MILP modelling has trouble solving difficult instances, while our decomposition method is more efficient for solving such instances. Our heuristic procedure provides good estimates for difficult instances.
doi_str_mv 10.1007/s10479-019-03387-9
format article
fullrecord <record><control><sourceid>gale_hal_p</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_hal_02318936v1</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A610369169</galeid><sourcerecordid>A610369169</sourcerecordid><originalsourceid>FETCH-LOGICAL-c501t-96c15bbfade207aa9114c0f051890af87298c27c3883fafe64e4f3947bbef6ee3</originalsourceid><addsrcrecordid>eNp9kV1rHCEUhqWk0E3aP9AroVeFTnLU-fJyCW0TWMhNci2Oe5x1ccatzpbk38fplHxACKJHD897OMeXkK8MzhlAc5EYlI0sgOUtRNsU8gNZsarhhczPE7ICXpVFJQR8Iqcp7QGAsbZakds1Hdw9bqkbJ-wxUu9G1JEeYuijHgY39nQIW_R-vtkQ6bRDaj3eu84jNQ_GO0P3oUu7cJhVOTt8Jh-t9gm__I9n5O7Xz9vLq2Jz8_v6cr0pTAVsKmRtWNV1Vm-RQ6O1ZKw0YKFirQRt24bL1vDGiLYVVlusSyytkGXTdWhrRHFGvi91d9qrQ3SDjg8qaKeu1hs154CLXEvUf1lmvy1s7vHPEdOk9uEYx9ye4iJTnDPePlO99qjcaMMUtRlcMmpdMxC1ZLXM1PkbVF5bHJwJI1qX868EP14IumPKn5zykVy_m1Kvjym9xvmCmxhSimifhmOgZr_V4rfKfqt_fqtZJBZRyvCYrXwe8B3VIxdEq54</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2331822128</pqid></control><display><type>article</type><title>A mixed integer linear programming modelling for the flexible cyclic jobshop problem</title><source>EBSCOhost Business Source Ultimate</source><source>ABI/INFORM global</source><source>Springer Nature</source><creator>Quinton, Félix ; Hamaz, Idir ; Houssin, Laurent</creator><creatorcontrib>Quinton, Félix ; Hamaz, Idir ; Houssin, Laurent</creatorcontrib><description>This paper addresses the Cyclic Jobshop Problem in a flexible context. The flexibility feature means that machines are able to perform several kinds of tasks. Hence, a solution of the scheduling problem does not only concern the starting times of the elementary tasks, but also the assignment of these tasks to a unique machine. The objective considered in this paper is the minimisation of the cycle time of a periodic schedule. We formulate the problem as a Mixed Integer Linear Problem and propose a Benders decomposition method along with a heuristic procedure to speed up the solving of large instances. It consists in reducing the number of machines available for each task. Results of numerical experiments on randomly generated instances show that the MILP modelling has trouble solving difficult instances, while our decomposition method is more efficient for solving such instances. Our heuristic procedure provides good estimates for difficult instances.</description><identifier>ISSN: 0254-5330</identifier><identifier>EISSN: 1572-9338</identifier><identifier>DOI: 10.1007/s10479-019-03387-9</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Benders decomposition ; Business and Management ; Combinatorics ; Computer Science ; Cycle time ; Flexible assembly systems ; Flexible manufacturing systems ; Heuristic methods ; Integer programming ; Linear programming ; Methods ; Mixed integer ; Operations Research ; Operations Research/Decision Theory ; Production scheduling ; S.I.: Project Management and Scheduling 2018 ; Schedules ; Scheduling (Management) ; Task scheduling ; Theory of Computation</subject><ispartof>Annals of operations research, 2020-02, Vol.285 (1-2), p.335-352</ispartof><rights>Springer Science+Business Media, LLC, part of Springer Nature 2019</rights><rights>COPYRIGHT 2020 Springer</rights><rights>Annals of Operations Research is a copyright of Springer, (2019). All Rights Reserved.</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c501t-96c15bbfade207aa9114c0f051890af87298c27c3883fafe64e4f3947bbef6ee3</citedby><cites>FETCH-LOGICAL-c501t-96c15bbfade207aa9114c0f051890af87298c27c3883fafe64e4f3947bbef6ee3</cites><orcidid>0000-0001-5975-7639 ; 0000-0003-4954-7958</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2331822128/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2331822128?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>230,314,776,780,881,11668,27903,27904,36039,44342,74641</link.rule.ids><backlink>$$Uhttps://laas.hal.science/hal-02318936$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Quinton, Félix</creatorcontrib><creatorcontrib>Hamaz, Idir</creatorcontrib><creatorcontrib>Houssin, Laurent</creatorcontrib><title>A mixed integer linear programming modelling for the flexible cyclic jobshop problem</title><title>Annals of operations research</title><addtitle>Ann Oper Res</addtitle><description>This paper addresses the Cyclic Jobshop Problem in a flexible context. The flexibility feature means that machines are able to perform several kinds of tasks. Hence, a solution of the scheduling problem does not only concern the starting times of the elementary tasks, but also the assignment of these tasks to a unique machine. The objective considered in this paper is the minimisation of the cycle time of a periodic schedule. We formulate the problem as a Mixed Integer Linear Problem and propose a Benders decomposition method along with a heuristic procedure to speed up the solving of large instances. It consists in reducing the number of machines available for each task. Results of numerical experiments on randomly generated instances show that the MILP modelling has trouble solving difficult instances, while our decomposition method is more efficient for solving such instances. Our heuristic procedure provides good estimates for difficult instances.</description><subject>Benders decomposition</subject><subject>Business and Management</subject><subject>Combinatorics</subject><subject>Computer Science</subject><subject>Cycle time</subject><subject>Flexible assembly systems</subject><subject>Flexible manufacturing systems</subject><subject>Heuristic methods</subject><subject>Integer programming</subject><subject>Linear programming</subject><subject>Methods</subject><subject>Mixed integer</subject><subject>Operations Research</subject><subject>Operations Research/Decision Theory</subject><subject>Production scheduling</subject><subject>S.I.: Project Management and Scheduling 2018</subject><subject>Schedules</subject><subject>Scheduling (Management)</subject><subject>Task scheduling</subject><subject>Theory of Computation</subject><issn>0254-5330</issn><issn>1572-9338</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp9kV1rHCEUhqWk0E3aP9AroVeFTnLU-fJyCW0TWMhNci2Oe5x1ccatzpbk38fplHxACKJHD897OMeXkK8MzhlAc5EYlI0sgOUtRNsU8gNZsarhhczPE7ICXpVFJQR8Iqcp7QGAsbZakds1Hdw9bqkbJ-wxUu9G1JEeYuijHgY39nQIW_R-vtkQ6bRDaj3eu84jNQ_GO0P3oUu7cJhVOTt8Jh-t9gm__I9n5O7Xz9vLq2Jz8_v6cr0pTAVsKmRtWNV1Vm-RQ6O1ZKw0YKFirQRt24bL1vDGiLYVVlusSyytkGXTdWhrRHFGvi91d9qrQ3SDjg8qaKeu1hs154CLXEvUf1lmvy1s7vHPEdOk9uEYx9ye4iJTnDPePlO99qjcaMMUtRlcMmpdMxC1ZLXM1PkbVF5bHJwJI1qX868EP14IumPKn5zykVy_m1Kvjym9xvmCmxhSimifhmOgZr_V4rfKfqt_fqtZJBZRyvCYrXwe8B3VIxdEq54</recordid><startdate>20200201</startdate><enddate>20200201</enddate><creator>Quinton, Félix</creator><creator>Hamaz, Idir</creator><creator>Houssin, Laurent</creator><general>Springer US</general><general>Springer</general><general>Springer Nature B.V</general><general>Springer Verlag</general><scope>AAYXX</scope><scope>CITATION</scope><scope>N95</scope><scope>3V.</scope><scope>7TA</scope><scope>7TB</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FR3</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JG9</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KR7</scope><scope>L.-</scope><scope>L6V</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope><scope>1XC</scope><scope>VOOES</scope><orcidid>https://orcid.org/0000-0001-5975-7639</orcidid><orcidid>https://orcid.org/0000-0003-4954-7958</orcidid></search><sort><creationdate>20200201</creationdate><title>A mixed integer linear programming modelling for the flexible cyclic jobshop problem</title><author>Quinton, Félix ; Hamaz, Idir ; Houssin, Laurent</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c501t-96c15bbfade207aa9114c0f051890af87298c27c3883fafe64e4f3947bbef6ee3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Benders decomposition</topic><topic>Business and Management</topic><topic>Combinatorics</topic><topic>Computer Science</topic><topic>Cycle time</topic><topic>Flexible assembly systems</topic><topic>Flexible manufacturing systems</topic><topic>Heuristic methods</topic><topic>Integer programming</topic><topic>Linear programming</topic><topic>Methods</topic><topic>Mixed integer</topic><topic>Operations Research</topic><topic>Operations Research/Decision Theory</topic><topic>Production scheduling</topic><topic>S.I.: Project Management and Scheduling 2018</topic><topic>Schedules</topic><topic>Scheduling (Management)</topic><topic>Task scheduling</topic><topic>Theory of Computation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Quinton, Félix</creatorcontrib><creatorcontrib>Hamaz, Idir</creatorcontrib><creatorcontrib>Houssin, Laurent</creatorcontrib><collection>CrossRef</collection><collection>Gale Business Insights</collection><collection>ProQuest Central (Corporate)</collection><collection>Materials Business File</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Engineering Research Database</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>Materials Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>Civil Engineering Abstracts</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>ABI/INFORM global</collection><collection>Computing Database</collection><collection>Science Database</collection><collection>Engineering Database</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><collection>Hyper Article en Ligne (HAL)</collection><collection>Hyper Article en Ligne (HAL) (Open Access)</collection><jtitle>Annals of operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Quinton, Félix</au><au>Hamaz, Idir</au><au>Houssin, Laurent</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A mixed integer linear programming modelling for the flexible cyclic jobshop problem</atitle><jtitle>Annals of operations research</jtitle><stitle>Ann Oper Res</stitle><date>2020-02-01</date><risdate>2020</risdate><volume>285</volume><issue>1-2</issue><spage>335</spage><epage>352</epage><pages>335-352</pages><issn>0254-5330</issn><eissn>1572-9338</eissn><abstract>This paper addresses the Cyclic Jobshop Problem in a flexible context. The flexibility feature means that machines are able to perform several kinds of tasks. Hence, a solution of the scheduling problem does not only concern the starting times of the elementary tasks, but also the assignment of these tasks to a unique machine. The objective considered in this paper is the minimisation of the cycle time of a periodic schedule. We formulate the problem as a Mixed Integer Linear Problem and propose a Benders decomposition method along with a heuristic procedure to speed up the solving of large instances. It consists in reducing the number of machines available for each task. Results of numerical experiments on randomly generated instances show that the MILP modelling has trouble solving difficult instances, while our decomposition method is more efficient for solving such instances. Our heuristic procedure provides good estimates for difficult instances.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s10479-019-03387-9</doi><tpages>18</tpages><orcidid>https://orcid.org/0000-0001-5975-7639</orcidid><orcidid>https://orcid.org/0000-0003-4954-7958</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0254-5330
ispartof Annals of operations research, 2020-02, Vol.285 (1-2), p.335-352
issn 0254-5330
1572-9338
language eng
recordid cdi_hal_primary_oai_HAL_hal_02318936v1
source EBSCOhost Business Source Ultimate; ABI/INFORM global; Springer Nature
subjects Benders decomposition
Business and Management
Combinatorics
Computer Science
Cycle time
Flexible assembly systems
Flexible manufacturing systems
Heuristic methods
Integer programming
Linear programming
Methods
Mixed integer
Operations Research
Operations Research/Decision Theory
Production scheduling
S.I.: Project Management and Scheduling 2018
Schedules
Scheduling (Management)
Task scheduling
Theory of Computation
title A mixed integer linear programming modelling for the flexible cyclic jobshop problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-26T18%3A16%3A28IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_hal_p&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20mixed%20integer%20linear%20programming%20modelling%20for%20the%20flexible%20cyclic%20jobshop%20problem&rft.jtitle=Annals%20of%20operations%20research&rft.au=Quinton,%20F%C3%A9lix&rft.date=2020-02-01&rft.volume=285&rft.issue=1-2&rft.spage=335&rft.epage=352&rft.pages=335-352&rft.issn=0254-5330&rft.eissn=1572-9338&rft_id=info:doi/10.1007/s10479-019-03387-9&rft_dat=%3Cgale_hal_p%3EA610369169%3C/gale_hal_p%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c501t-96c15bbfade207aa9114c0f051890af87298c27c3883fafe64e4f3947bbef6ee3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2331822128&rft_id=info:pmid/&rft_galeid=A610369169&rfr_iscdi=true