Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Foundations of Computing and Decision Sciences

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: due-date assignment

Sortuj według:

Ogranicz wyniki do:

Scheduling and due-date assignment problems with job rejection

Mosheiov G., Sarig A.

Foundations of Computing and Decision Sciences

2009

Vol. 34, No. 3

193-208

Scheduling with rejection reflects a very common scenario, where the scheduler may decide not to process a job if it is not profitable. We study the option of rejection in several popular and well-known scheduling and due-date assignment problems. A number of settings are considered: due-date and due-window assignment problems with job-independent costs, a due-date assignment problem with job-dependent weights and unit jobs, minimum total weighted earliness and tardiness cost with job-dependent and symmetric weights (known as TWET), and several classical scheduling problems (minimum makespan, flow-time, earliness-tardiness) with position-dependent processing times. All problems (excluding TWET) are shown to have a polynomial time solution. For the (NP-hard) TWET, a pseudo-polynomial time dynamic programming algorithm is introduced and tested numerically.

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.