Hits:
Indexed by:Journal Papers
Date of Publication:2015-07-15
Journal:APPLIED MATHEMATICAL MODELLING
Included Journals:SCIE、EI
Volume:39
Issue:14
Page Number:4013-4021
ISSN No.:0307-904X
Key Words:Scheduling; Deteriorating jobs; Learning effect; Makespan; Total completion time; Single-machine
Abstract:The paper is devoted to some single-machine scheduling problems with variable job processing times. The objectives are to minimize the makespan (i.e., the maximum completion time of all jobs), and to minimize the total completion time. For some special cases, we show that these problems can be solved in polynomial time. For some another special cases of the makespan and the total completion time minimization problems, we prove that an optimal schedule has an V-shape property in terms of processing times. We also propose a heuristic algorithm by utilizing the V-shape property. (C) 2014 Elsevier Inc. All rights reserved.