Parallel machine scheduling problem to minimize the earliness/tardiness costs with learning effect and deteriorating jobs

TOKSARI M. D., GÜNER E.

JOURNAL OF INTELLIGENT MANUFACTURING, vol.21, no.6, pp.843-851, 2010 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 21 Issue: 6
  • Publication Date: 2010
  • Doi Number: 10.1007/s10845-009-0260-3
  • Journal Name: JOURNAL OF INTELLIGENT MANUFACTURING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.843-851
  • Keywords: Earliness/tardiness, Learning effect, Deterioration jobs, V-shaped property, Parallel machine, Sequence-dependent setup time, Common due date, DEPENDENT PROCESSING TIMES, EARLINESS-TARDINESS COSTS, TOTAL COMPLETION-TIME, COMMON DUE-DATE, SINGLE-MACHINE, FLOW-SHOP, LINEAR DETERIORATION, SHAPED POLICIES, PENALTIES, IMPACT
  • Gazi University Affiliated: Yes

Abstract

The focus of this work is to analyze parallel machine earliness/tardiness (ET) scheduling problem with simultaneous effects of learning and linear deterioration, sequence-dependent setups, and a common due-date for all jobs. By the effects of learning and linear deterioration, we mean that the processing time of a job is defined by an increasing function of its starting time and a decreasing function of the position in the sequence. We develop a mixed integer programming formulation for the problem and show that the optimal sequence is V-shaped: all jobs scheduled before the shortest jobs and all jobs scheduled after the shortest job are in a non-increasing and non-decreasing order of processing times, respectively. The developed model allows sequence-dependent setups and sequence-dependent early/tardy penalties. The illustrative example with 11 jobs for 2 machines and 3 machines shows that the model can easily provide the optimal solution, which is V-shaped, for problem.