Minimizing the expected weighted number of tardy jobs in stochastic flow shops
type: Item
instance of: scholarly article
title: Minimizing the expected weighted number of tardy jobs in stochastic flow shops
zbMATH Open document ID: 0633.90028
DOI: 10.1016/0167-6377(86)90084-2
published in: Operations Research Letters
publication date: 1986-01-01T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/1783
review text: Two stochastic scheduling models are considered: one with just a single machine, the other 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 much harder case of a flow shop with an arbitrary number of machines and identically distributed due dates for all jobs, the following intuitively appealing results are proved: (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. Extensive use is made of arguments based on pairwise interchanges.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 4031375
zbMATH Keywords: stochastic scheduling
zbMATH Keywords: single machine
zbMATH Keywords: flow shop
zbMATH Keywords: arbitrary number of machines
zbMATH Keywords: due dates
zbMATH Keywords: expected weighted number of tardy jobs
zbMATH Keywords: optimality conditions
author: Onno Boxma
author: Frank G. Forst
reviewed by: Kevin D. Glazebrook
MaRDI profile type: Publication
OpenAlex ID: W2045065221
cites work: Scheduling to Minimize the Number of Late Jobs When Set-Up and Processing Times are Uncertain
cites work: On stochastic scheduling problems with due dates
cites work: Q4142699
cites work: A polynomial time algorithm for a chance-constrained single machine scheduling problem
cites work: Note—On Baluts Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem
cites work: AN EFFICIENT ALGORITHM FOR A CHANCE-CONSTRAINED SCHEDULING PROBLEM
cites work: Stochastic Scheduling with Release Dates and Due Dates
cites work: Q4127768
description: scientific article; zbMATH DE number 4031375