History-dependent scheduling: Models and algorithms for scheduling with general precedence and sequence dependence. (December 2015)

• Record Type: Journal Article
• Authors: Dayama, Niraj Ramesh; Krishnamoorthy, Mohan; Ernst, Andreas; Rangaraj, Narayan; Narayanan, Vishnu
• Is Part Of: Computers & operations research. Volume 64(2015)
• Page Start: 245
• Page End: 261
• Publication Date: 2015-12
• Subjects: Sequence-dependent scheduling -- Crane scheduling -- Fixed interval scheduling -- History-dependent scheduling -- Combinatorial optimization -- Integer programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.06.007
• Languages: English
• ISSNs: 0305-0548

Abstract

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. Abstract : Highlights: Detailed explanation of differences between GPSP and Block-world problem has been submitted within the response document. Summary of differences between GPSP and block-world problem has been included in the paper. Justification for using only first log( n ) and not all i, j, K combinations has been included in the paper. Mistakes in write-up have been corrected as pointed out by reviewers.