Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and tot...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2007-02, Vol.177 (1), p.638-645
Main Authors: Wang, Ji-Bo, Xia, Zun-Quan
Format: Article
Language:English
Subjects:
Applied sciences
Controllable processing times
Exact sciences and technology
Job shops
Machinery
Operational research and scientific management
Operational research. Management science
Scheduling
Scheduling algorithms
Scheduling, sequencing
Single machine
Studies
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 single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O( n log n) algorithm to obtain the optimal solution.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2005.10.054