𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A branch and bound approach for single machine scheduling with earliness and tardiness penalties

✍ Scribed by Pei Chann Chang

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
660 KB
Volume
37
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis

An n job, single machine scheduling problem in which each job has a distinct due date, dd, is studied in this paper. The objective is to determine an optimal schedule Ir Β° for a set of jobs, S, such that the total absolute deviation of the schedule is minimized. This objective function is based on the due date value and on the earliness or tardiness of each job in the selected sequence. This paper presents a bounding scheme for the calculation of different lower bounds based on the overlap elimination procedure on a Just-ln-Time schedule. Properties and theorems of the overlap elimination procedure are also provided. Finally, a numerical example is illustrated and some extensions of the approach are also discussed.

πŸ“œ SIMILAR VOLUMES

Adjacent orderings in single-machine sch
Adjacent orderings in single-machine scheduling with earliness and tardiness penalties
✍ Wlodzimierz Szwarc πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 771 KB

This article deals with a single-machine n job earliness-tardiness model with jobindependent penalties. It demonstrates that the arrangement of adjacent jobs in an optimal schedule depends on a critical value of the start times. Based on these precedence relations, the article develops criteria unde

Minimizing weighted earliness and tardin
Minimizing weighted earliness and tardiness penalties in single-machine scheduling with idle time permitted
✍ Jaw-Yeh Chen; Sheng-Fuu Lin πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 169 KB

## Abstract In this paper, a single‐machine scheduling problem with weighted earliness and tardiness penalties is considered. Idle time between two adjacent jobs is permitted and due dates of jobs could be unequal. The dominance rules are utilized to develop a relationship matrix, which allows a br