Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem
| Autor: | H.M. Soroush |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Mathematical optimization
Information Systems and Management Single-machine scheduling General Computer Science General problem Workload Management Science and Operations Research Industrial and Manufacturing Engineering Stochastic programming Scheduling (computing) Due date Production manager Modeling and Simulation Algorithm Mathematics |
| Zdroj: | European Journal of Operational Research. 181:266-287 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2006.05.036 |
| Popis: | We study a static stochastic single machine scheduling problem in which jobs have random processing times with arbitrary distributions, due dates are known with certainty, and fixed individual penalties (or weights) are imposed on both early and tardy jobs. The objective is to find an optimal sequence that minimizes the expected total weighted number of early and tardy jobs. The general problem is NP-hard to solve; however, in this paper, we develop certain conditions under which the problem is solvable exactly. An efficient heuristic is also introduced to find a candidate for the optimal sequence of the general problem. Our illustrative examples and computational results demonstrate that the heuristic performs well in identifying either optimal sequences or good candidates with low errors. Furthermore, we show that special cases of the problem studied here reduce to some classical stochastic single machine scheduling problems including the problem of minimizing the expected weighted number of early jobs and the problem of minimizing the expected weighted number of tardy jobs which are both solvable by the proposed exact or heuristic methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect