Single-Machine Scheduling with Job-Position-Dependent Learning and Time-Dependent Deterioration

Yunqiang Yin, Min Liu, Min Liu, Jinghua Hao, Jinghua Hao, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

64 Scopus citations

Abstract

Job deterioration and learning co-exist in many realistic scheduling situations. This paper introduces a general scheduling model that considers the effects of position-dependent learning and time-dependent deterioration simultaneously. In the proposed model, the actual processing time of a job depends not only on the total processing time of the jobs already processed but also on its scheduled position. This paper focuses on the singlemachine scheduling problems with the objectives of minimizing the makespan, total completion time, total weighted completion time, discounted total weighted completion time, and maximum lateness based on the proposed model, respectively. It shows that they are polynomially solvable and optimal under certain conditions. Additionally, it presents some approximation algorithms based on the optimal schedules for the corresponding single-machine scheduling problems and analyzes their worst case error bound.

Original languageEnglish (US)
Pages (from-to)192-200
Number of pages9
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans
Volume42
Issue number1
DOIs
StatePublished - Jan 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Approximation methods
  • manufacturing scheduling
  • modeling

Fingerprint

Dive into the research topics of 'Single-Machine Scheduling with Job-Position-Dependent Learning and Time-Dependent Deterioration'. Together they form a unique fingerprint.

Cite this