Minimizing the expected weighted number of tardy jobs in stochastic flow shops

This paper is devoted to two types of stochastic scheduling problems, one involving a single machine and the other involving a flow shop consisting of an arbitrary number of machines. In both problem types, all jobs to be processed have due dates, and the objective is to find a job sequence that min...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 1986-08, Vol.5 (3), p.119-126
Main Authors: Boxma, O.J., Forst, F.G.
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
flow shop
Operational research and scientific management
Operational research. Management science
Scheduling, sequencing
stochastic sequencing
tardiness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper is devoted to two types of stochastic scheduling problems, one involving a single machine and the other involving a flow shop consisting of an arbitrary number of machines. In both problem types, all jobs to be processed have due dates, and the objective is to find a job sequence that minimizes the expected weighted number of tardy jobs. For the single-machine case, sufficient optimality conditions for job sequences are derived for various choices of due date and processing time distributions. For the case of a flow shop with an arbitrary number of machines and identically distributed due dates for all jobs, we prove the following intuitively appealing results: (i) when all jobs have the same processing time distributions, the expected weighted number of tardy jobs is minimized by sequencing the jobs in decreasing order of the weights, (ii) when all weights are equal, the jobs should be sequenced according to an increasing stochastic ordering of the processing time distributions.
ISSN:0167-6377
1872-7468
DOI:10.1016/0167-6377(86)90084-2