Single-machine total completion time scheduling with a time-dependent deterioration

In this paper, we consider the single-machine scheduling problems with a time-dependent deterioration. By the time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. The objec...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematical modelling 2011-03, Vol.35 (3), p.1506-1511
Main Authors: Wang, Ji-Bo, Sun, Lin-Hui, Sun, Lin-Yan
Format: Article
Language:English
Subjects:
Applied sciences
Completion time
Deteriorating jobs
Deterioration
Exact sciences and technology
Heuristic methods
Inventory control, production control. Distribution
Mathematical analysis
Mathematical models
Mathematical programming
Mixed integer
Operational research and scientific management
Operational research. Management science
Programming
Scheduling
Scheduling, sequencing
Single-machine
Time-dependent
Total completion time
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider the single-machine scheduling problems with a time-dependent deterioration. By the time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total completion time. We develop a mixed integer programming formulation for the problem. The complexity status of this problem remains open. Hence, we use the smallest normal processing time (SPT) first rule as a heuristic algorithm for the general cases and analyze its worst-case error bound. Two heuristic algorithms utilize the V-shaped property are also proposed to solve the problem. Computational results are presented to evaluate the performance of the proposed algorithms.
ISSN:0307-904X
DOI:10.1016/j.apm.2010.09.028