Dolgui, Alexandre, Gordon, Valery and Strusevich, Vitaly (2012) Single machine scheduling with precedence constraints and positionally dependent processing times. Computers and Operations Research, 39 (6). pp. 1218-1224. ISSN 0305-0548 (doi:10.1016/j.cor.2010.06.004)

Full text not available from this repository.

Abstract

In many real-life situations the processing conditions in scheduling models cannot be viewed as given constants since they vary over time thereby affecting actual durations of jobs. We consider single machine scheduling problems of minimizing the makespan in which the processing time of a job depends on its position (with either cumulative deterioration or exponential learning). It is often found in practice that some products are manufactured in a certain order implied, for example, by technological, marketing or assembly requirements. This can be modeled by imposing precedence constraints on the set of jobs. We consider scheduling models with positional deterioration or learning under precedence constraints that are built up iteratively from the prime partially ordered sets of a bounded width (this class of precedence constraints includes, in particular, seriesparallel precedence constraints). We show that objective functions of the considered problems satisfy the job module property and possess the recursion property. As a result, the problems under consideration are solvable in polynomial time.

Item Type:	Article
Additional Information:	[1] Published in Computers & Operations Research, Volume 39, Issue 6, (June 2012) - Special Issue on Scheduling in Manufacturing Systems.
Uncontrolled Keywords:	deterioration, learning, positionally dependent processing time, precedence constraints, scheduling
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher
Last Modified:	14 Oct 2016 09:18
URI:	http://gala.gre.ac.uk/id/eprint/7296

Actions (login required)

View Item