✦ LIBER ✦

A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop

✍ Scribed by Michael Pinedo; Marcos Singer

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 165 KB
Volume: 46
Category: Article
ISSN: 0894-069X
DOI: 10.1002/(sici)1520-6750(199902)46:1<1::aid-nav1>3.0.co;2-#

No coin nor oath required. For personal study only.

✦ Synopsis

We present a shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. The method decomposes the job shop into a number of single-machine subproblems that are solved one after another. Each machine is scheduled according to the solution of its corresponding subproblem. The order in which the single machine subproblems are solved has a significant impact on the quality of the overall solution and on the time required to obtain this solution. We therefore test a number of different orders for solving the subproblems. Computational results on 66 instances with ten jobs and ten machines show that our heuristic yields solutions that are close to optimal, and it clearly outperforms a well-known dispatching rule enhanced with backtracking mechanisms.

📜 SIMILAR VOLUMES

A large step random walk for minimizing

A large step random walk for minimizing total weighted tardiness in a job shop

✍ Stephan Kreipl 📂 Article 📅 2000 🏛 Springer US 🌐 English ⚖ 116 KB

We consider a job shop with m machines. There are n jobs and each job has a speciÿed sequence to be processed by the machines. Job j has release date rj, due date dj, weight wj and processing time pij on machine i (1; : : : ; m). The objective is to minimize the total weighted tardiness of the n job

Heuristics for minimizing total weighted

Heuristics for minimizing total weighted tardiness in flexible flow shops

✍ Ya Yang; Stephan Kreipl; Michael Pinedo 📂 Article 📅 2000 🏛 Springer US 🌐 English ⚖ 156 KB 👁 1 views

Consider a #exible #ow shop with s stages in series and at each stage a number of identical machines in parallel. There are n jobs to be processed and each job has to go through the stages following the same route. Job j has release date r H , due date d H , weight w H and a processing time p HJ at