𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Exact and heuristic algorithms for parallel-machine scheduling with DeJong’s learning effect

✍ Scribed by Dariusz Okołowski; Stanisław Gawiejnowicz

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
296 KB
Volume
59
Category
Article
ISSN
0360-8352

No coin nor oath required. For personal study only.

✦ Synopsis

a b s t r a c t

We consider a parallel-machine scheduling problem with a learning effect and the makespan objective. The impact of the learning effect on job processing times is modelled by the general DeJong's learning curve. For this NP-hard problem we propose two exact algorithms: a sequential branch-and-bound algorithm and a parallel branch-and-bound algorithm. We also present the results of experimental evaluation of these algorithms on a computational cluster. Finally, we use the exact algorithms to estimate the performance of two greedy heuristic scheduling algorithms for the problem.

📜 SIMILAR VOLUMES

Genetic algorithms for the job-shop sche
Genetic algorithms for the job-shop scheduling problem with unrelated parallel constraints: Heuristic mixing method machines and precedence
✍ Fatima Ghedjati 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 360 KB

In this paper, we are interested in job-shop scheduling problems with several unrelated parallel machines and precedence constraints between the operations of the jobs (with either linear or non-linear process routings). The objective is to minimize the maximum completion time (Cmax). We propose an

Search heuristics for a parallel machine
Search heuristics for a parallel machine scheduling problem with ready times and due dates
✍ Moon-Won Park; Yeong-Dae Kim 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 348 KB

We consider a problem of scheduling orders on identical parallel machines An order can be released after a given ready time and must be completed before its due date An order is split into multiple jobs (batches) and a job is processed on one of the parallel machines The objective of the scheduling

Some unrelated parallel machine scheduli
Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects
✍ Wen-Hung Kuo; Chou-Jung Hsu; Dar-Li Yang 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 205 KB

Total absolute deviation of job completion times Total load a b s t r a c t In this paper, we study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup ti

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