History-dependent scheduling: Models and algorithms for scheduling with general precedence and sequence dependence

Niraj Ramesh Dayama, Mohan Krishnamoorthy, Andreas Tilman Ernst, Narayan Rangaraj, Vishnu Narayanan

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

Abstract

In this paper, we extend job scheduling models to include aspects of history-dependent scheduling, where setup times for a job are affected by the aggregate activities of all predecessors of that job. Traditional approaches to machine scheduling typically address objectives and constraints that govern the relative sequence of jobs being executed using available resources. This paper optimises the operations of multiple unrelated resources to address sequential and history-dependent job scheduling constraints along with time window restrictions. We denote this consolidated problem as the general precedence scheduling problem (GPSP).We present several applications of the GPSP and show that many problems in the literature can be represented as special cases of history-dependent scheduling. We design new ways to model this class of problems and then proceed to formulate it as an integer program. We develop specialized algorithms to solve such problems. An extensive computational analysis over a diverse family of problem data instances demonstrates the efficacy of the novel approaches and algorithms introduced in this paper.
Original languageEnglish
Pages (from-to)245 - 261
Number of pages17
JournalComputers and Operations Research
Volume64
DOIs
Publication statusPublished - 2015

Cite this