A heuristic for the stochastic single-machine problem with E/T costs (2013)
- Autor USP: RONCONI, DEBORA PRETTI - EP
- Unidade: EP
- Subjects: HEURÍSTICA; PESQUISA OPERACIONAL
- Language: Inglês
- Abstract: This paper addresses the problem of simultaneous due-date determination and sequencing of a set of jobs on a stochastic single machine environment with distinct job earliness and tardiness penalty costs. It was assumed that the jobs processing times are statistically independent and follow a normal distribution whose mean and variance are given and not necessarily integer values. The objective is to determine the optimal sequence and the optimal deterministic integer due dates which jointly minimize the expected total earliness and tardiness cost. Previous theoretical results regarding normally distributed processing times and expected values of earliness and tardiness costs are reviewed. It is proposed an efficient insertion-based construction heuristic to find candidates for the optimal sequence with polynomial time complexity. It was shown that the heuristic solution method includes safety time and the sequence obtained remains the same regardless of disruptions, meaning that the result is robust. Illustrative examples and computational experiments reveal that the proposed heuristic procedure performs well and is nearly always optimal. The heuristic was applied for 680 different problems with sizes between 5 and 12 jobs, resulting in an optimality percentage of 99.85%. When applied to a sample of 480 problems with sizes between 13 and 1000 jobs, it yielded at least the same results found in the literature, providing solutions with better costs in more than 80% of cases. Furthermore, it was proved that the heuristic is asymptotically optimal, so it can be recommended for problems of any size
- Título do periódico: Proceedings. Challenges for sustainable operations
- Conference titles: International Conference on Production Research - ICPR
ABNTLEMOS, Rafael de Freitas; RONCONI, Débora Pretti. A heuristic for the stochastic single-machine problem with E/T costs. Anais.. S.l: ABEPRO, 2013.
APALemos, R. de F., & Ronconi, D. P. (2013). A heuristic for the stochastic single-machine problem with E/T costs. In Proceedings. Challenges for sustainable operations. S.l: ABEPRO.
NLMLemos R de F, Ronconi DP. A heuristic for the stochastic single-machine problem with E/T costs. Proceedings. Challenges for sustainable operations. 2013 ;
VancouverLemos R de F, Ronconi DP. A heuristic for the stochastic single-machine problem with E/T costs. Proceedings. Challenges for sustainable operations. 2013 ;
- Heurísticas construtivas para a minimização do atraso total no ambiente job shop flexível
- Busca tabu para a minimização do tempo total de atraso no problema de flowshop
- Minimising total tardiness on a flowshop with blocking in process
- Tópicos em métodos de otimização para programação de tarefas e problemas correlatos
- Scatter Search para programação de tarefas em uma máquina com penalidades de adiantamento e atraso e data de entrega comum
- Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date.
- Uma heurística construtiva para o problema de minimização do atraso total no ambiente flowshop com buffer zero
- Regras de prioridade eficientes que exploram características do Job Shop Flexível para a minimização do atraso total
- Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming
- New heuristics for total tardiness minimization in a flexible flowshop
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas