History-dependent scheduling: Models and algorithms for scheduling with general precedence and sequence dependence
DSpace at IIT Bombay
View Archive InfoField | 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
|
|