Resource title

Exact and approximation algorithms for the tactical fixed interval scheduling problem

Resource image

image for OpenScout resource :: Exact and approximation algorithms for the tactical fixed interval scheduling problem

Resource description

The Tactical Fixed Interval Scheduling Problem (TFISP) is the problem of determining the minimum number of parallel non-identical machines, such that a feasible schedule exists for a given set of jobs. In TFISP each job must be carried out in a perspecified time interval and belongs to a specific job class. The problem is complicated by the restrictions that (i) each machine can handle one job at a time only, (ii) each machine can handle jobs from a subset of the job classes only, and (iii) preemption is not allowed. In this paper we discuss the occurrence of TFISP in practice, we analyse the computational complexity of TFISP, and we present exact and approximation algorithms for solving TFISP. The paper is concluded with a computational study

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

application/pdf

Resource resource URL

http://flora.insead.edu/fichiersti_wp/Inseadwp1994/94-04.pdf

Resource license

Copyright INSEAD. All rights reserved