no problema de sequenciamento de trabalho, o objetivo é encontrar a sequência de trabalhos,que é concluída dentro de seus prazos e dar lucro máximo.
se um conjunto de N empregos são dadas que estão associados com prazos e lucro é ganho e um trabalho é concluído até o seu prazo. Esses trabalhos precisam ser ordenados de tal forma que haja lucro máximo.
vamos dar um exemplo. Como mostrado na figura 1.1, uma série de trabalhos é dada onde cada trabalho tem um prazo e lucro associado se o trabalho for concluído antes do prazo. Também é dado que cada trabalho leva uma única unidade de tempo, portanto, o prazo mínimo possível para qualquer trabalho é 1. Como maximizar o lucro total se apenas um trabalho puder ser agendado por vez.
Uma solução simples é gerar todos os subconjuntos do conjunto dado de emprego e verifique o subconjunto para a viabilidade de empregos no subconjunto. Acompanhe o lucro máximo entre todos os subconjuntos viáveis. A complexidade Temporal desta solução é exponencial.Também podemos resolver esse problema usando o método ganancioso, que é mais ideal do que uma solução simples.Então, vamos resolver este problema através do método ganancioso.
Para resolver o trabalho de seqüenciamento problema através do método guloso siga este passos:
- Classificar todos os trabalhos em ordem decrescente de lucro.
- inicializar a sequência de resultados como primeiro trabalho em trabalhos classificados.
- faça o seguinte para os empregos n-1 restantes.
- se o trabalho atual puder caber na sequência de resultados atual sem perder o prazo, adicione o trabalho atual ao resultado. Então ignore o trabalho atual.
como você pode ver na figura 1.1 os trabalhos já estão em ordem decrescente de lucro.Aqui, o trabalho 1 tem o maior lucro e o prazo é 3, portanto, defina esse trabalho entre 2-3, conforme mostrado na figura 1.2.O trabalho 2 tem o segundo maior lucro e o prazo é 4, então defina esse trabalho entre 3-4 e faça o mesmo com todos jobs.So a sequência final é J4-J3-J1-J2 e o lucro total é 110.
você pode preferir o código para este algoritmo em https://www.geeksforgeeks.org/job-sequencing-problem.
a complexidade Temporal desta solução é O (n2). ele pode ser otimizado pela estrutura de dados disjunta.
espero que você goste do artigo.Obrigado:)
