Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2013-02-01

Journal: APPLIED MATHEMATICAL MODELLING

Included Journals: EI、SCIE

Volume: 37

Issue: 3

Page Number: 649-658

ISSN: 0307-904X

Key Words: Scheduling; Single-machine; Position-dependent processing times; Parallel chains; Series-parallel graph

Abstract: In this paper we consider single-machine scheduling problems with position-dependent processing times, i.e., jobs whose processing times are an increasing or decreasing function of their positions in a processing sequence. In addition, the jobs are related by parallel chains and a series-parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan polynomial algorithms exist. (C) 2012 Elsevier Inc. All rights reserved.