✦ LIBER ✦

Exact algorithms for scheduling multiple families of jobs on parallel machines

✍ Scribed by Zhi-Long Chen; Warren B. Powell

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 140 KB
Volume: 50
Category: Article
ISSN: 0894-069X
DOI: 10.1002/nav.10091

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 823–840, 2003.

📜 SIMILAR VOLUMES

Online real-time preemptive scheduling o

Online real-time preemptive scheduling of jobs with deadlines on multiple machines

✍ Bhaskar Das Gupta; Michael A. Palis 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 139 KB

In this paper, we derive bounds on performance guarantees of online algorithms for real-time preemptive scheduling of jobs with deadlines on K machines when jobs are characterized in terms of their minimum stretch factor (or, equivalently, their maximum execution rate r = 1= ). We consider two well-

A branch-and-price algorithm for paralle

A branch-and-price algorithm for parallel machine scheduling with time windows and job priorities

✍ Jonathan F. Bard; Siwate Rojanasoonthon 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 1 views

## Abstract This paper presents a branch‐and‐price algorithm for scheduling __n__ jobs on __m__ nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of __ρ__ priority classes and may require two operations. The objective i

Approximation Algorithms for Precedence-

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds

✍ Fabián A Chudak; David B Shmoys 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 141 KB

A heuristic for maximizing the number of

A heuristic for maximizing the number of on-time jobs on two uniform parallel machines

✍ Christos Koulamas; George J. Kyparisis 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

Approximation algorithms for minimizing

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

✍ Joseph Y-T. Leung; Haibing Li; Michael Pinedo 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB

## Abstract We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is re

Polynomial time algorithms for minimizin

Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times

✍ Philippe Baptiste 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 102 KB 👁 2 views

We study the problem of minimizing the weighted number of late jobs to be scheduled on a single machine when processing times are equal. In this paper, we show that this problem, as well as its preemptive variant, are strongly polynomial. When preemption is not allowed ( 1"p H "p, r H " w H ; H ), t