Minimizing flow time on a single machine with job classes and setup times

A. J. Mason and E. J. Anderson

Naval Research Logistics (NRL), 1991, vol. 38, issue 3, 333-350

Abstract: We examine the static sequencing problem of ordering the processing of jobs on a single machine so as to minimize the average weighted flow time. It is assumed that all jobs have zero ready times, and that the jobs are grouped into classes with the property that setup tasks are only required when processing switches from jobs of one class to jobs of another class. The time required for each setup task is given by the sum of a setdown time from the previous class and a setup time for the new class. We show that an algorithm presented in the literature for solving a special case of this problem gives suboptimal solutions. A number of properties of the optimal solution are derived, and their use in algorithms is evaluated. Computational results are presented for both a branch‐and‐bound procedure and a simpler depth‐first search.

Date: 1991
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199106)38:33.0.CO;2-0

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:38:y:1991:i:3:p:333-350

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().