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

• Published in: Computers & industrial engineering 2019-03, Vol.129, p.251-258
• Main Authors: da Silva, Nathália Cristina Ortiz, Scarpin, Cassius Tadeu, Pécora, José Eduardo, Ruiz, Angel
• Format: Article
• Language: English
• Subjects: Insertion of new orders; Online scheduling; Sequence-dependent setup time; Simulation; Withdrawal of existing jobs
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2019.01.038

•Tackles a production schedule problem with task’s inclusion/exclusion in real time.•Solve each reschedule using operational heuristics and exact method.•Compares the results with a Perfect Information Model.•The reschedule of exact model shows promising computational results.•Proves the usefulness of optimization in this kind of production management. 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.