Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine

► Scheduling with time variable processing times. ► Review of applications. ► Position-dependent penalties. ► Special linear assignment models. ► Very fast algorithms. We consider scheduling problems with learning/deterioration effects and time-dependent processing times on a single machine, with or...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2013-03, Vol.225 (3), p.547-551
Main Authors: Qian, Jianbo, Steiner, George
Format: Article
Language:English
Subjects:
Algorithms
Assignment problem
Deterioration
Due date assignment
Due dates
Job shops
Learning
Learning/deterioration effect
Mathematical analysis
Matrices
Matrix
Operational research
Scheduling
Scheduling algorithms
Studies
Time-dependent
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:► Scheduling with time variable processing times. ► Review of applications. ► Position-dependent penalties. ► Special linear assignment models. ► Very fast algorithms. We consider scheduling problems with learning/deterioration effects and time-dependent processing times on a single machine, with or without due date assignment considerations. By reducing them to a special assignment problem on product matrices, we solve all these problems in near-linear time. This improves the time complexity of previous algorithms for some scheduling problems and establishes the fast polynomial solvability for several other problems.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2012.09.013