𝔖 Bobbio Scriptorium
✦   LIBER   ✦

One-machine job-scheduling with non-constant capacity — Minimizing weighted completion times

✍ Scribed by H.F. Amaddeo; W.M. Nawijn; A. van Harten

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
720 KB
Volume
102
Category
Article
ISSN
0377-2217

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some special cases where this condition is also sufficient. We prove that the problem is NP-complete, A branch-and-bound algorithm is developed for the case when the capacity function is a step function. Computational results for 1000 test problems are presented. (~) 1997 Elsevier Science B.V.

📜 SIMILAR VOLUMES

Maximizing the weighted number of on-tim
Maximizing the weighted number of on-time jobs in single machine scheduling with time windows
✍ C. Koulamas 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 541 KB

The problem of maximizing the weighted number of on-time jobs on a single machine with time windows (STW) is shown to be strongly NP-hard. An efficient. heuristic is presented for STW. Computational experiments indicate that the performance of the heuristic is quite good.

Scheduling identical jobs with unequal r
Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness
✍ Maged M. Dessouky 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 308 KB

AbstractÐWe consider the problem of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum lateness. This paper develops a branch-and-bound procedure that optimally solves the problem and introduces six simple single-pass heuristic procedures that