Record Details

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

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title History-dependent scheduling: Models and algorithms for scheduling with general precedence and sequence dependence
 
Creator DAYAMA, NR
KRISHNAMOORTHY, M
ERNST, A
RANGARAJ, N
NARAYANAN, V
 
Subject TRAVELING SALESMAN PROBLEM
BRANCH-AND-CUT
TIME WINDOWS
DELIVERY PROBLEM
PICKUP
Sequence-dependent scheduling
Crane scheduling
Fixed interval scheduling
History-dependent scheduling
Combinatorial optimization
Integer programming
 
Description 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. (C) 2015 Elsevier Ltd. All rights reserved.
 
Publisher PERGAMON-ELSEVIER SCIENCE LTD
 
Date 2016-01-14T13:30:49Z
2016-01-14T13:30:49Z
2015
 
Type Article
 
Identifier COMPUTERS & OPERATIONS RESEARCH, 64,245-261
0305-0548
1873-765X
http://dx.doi.org/10.1016/j.cor.2015.06.007
http://dspace.library.iitb.ac.in/jspui/handle/100/17620
 
Language en