Online single machine scheduling with setup times depending on the jobs' sequence

Authors: Ortiz Da Silva, Nathália Cristina; Tadeu Scarpin, Cassius; Pécora Junior, José Eduardo; Ruiz, Angel
Abstract: This paper considers a dynamic scheduling problem where the set of jobs to perform is modified by the arrival of events (customer orders) requiring the execution of a new job or the cancellation of a previously ordered one once the production has begun. To tackle this dynamic context, we propose an online approach that reconsiders the actual schedule every time a new event arrives. In particular, upon an event arrival, the remaining unprocessed jobs as well as the new event are scheduled by a Mixed Integer Linear Programming (MILP) formulation that aims to minimize the makespan. We compare the results of this approach, which we will refer to as Exact Approach (EA), to several job insertion methods broadly used in practice, and to a Perfect Information Model (PIM), which assumes that the events’ release dates are also known before starting the production. Extensive numerical experiments allow estimating the “value of the information” or, in other words, the cost of uncertainty in terms of total setup time increase as well as the relative performance of the considered methods.
Document Type: Article de recherche
Issue Date: 22 January 2019
Open Access Date: 22 January 2022
Document version: AM
Permalink: http://hdl.handle.net/20.500.11794/37502
This document was published in: Computers & Industrial Engineering, Vol. 129, 251–258 (2019)
https://doi.org/10.1016/j.cie.2019.01.038
Elsevier Science
Alternative version: 10.1016/j.cie.2019.01.038
Collection:Articles publiés dans des revues avec comité de lecture

Files in this item:
SizeFormat 
ManuscriptCAIE-Rev2-Final.docx
122.78 kBMicrosoft Word XML    Request a copy
All documents in CorpusUL are protected by Copyright Act of Canada.