Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Slack due date assignment and scheduling stochastic jobs on a single machine

Soroush H. M.

Foundations of Computing and Decision Sciences

2007

Vol. 32, No. 2

153-181

This paper solves the general case of the stochastic single machine scheduling problem where processing times are random variables and due dates are assigned using the slack method. Its objective is to identify the optimal sequence and optimal due dates which minimize the expected total weighted cost of assigning and missing due dates, with no restriction imposed on either cost. The paper presents an exact two-stage algorithm. The first stage (i) utilizes an adjacent precedence relation structure to determine an initial ordering of jobs, (ii) investigates the optimality of the initial job ordering, and (iii) when it cannot prove optimality. it tries to improve the initial ordering by moving jobs from their current positions to any other positions that ensure the precedence relations hold; thus, obtains an incumbent solution. The second stage, which uses the incumbent to show its optimality or search for the optimal solution, is a branch and bound. It utilizes the expected cost of the incumbent as an initial upper bound. It avoids investigating dominated branches by using the job precedence relations; thus, greatly reduces the size of the tree. Extensive computational results show that the incumbent solution obtained in the first stage of the algorithm provides a very tight upper bound cost which fathoms a significant number of non-dominated solutions in the second stage; thus, the proposed algorithm can solve large problems quickly on PC.