Nesta tese, dois diferentes problemas de programação da produção são abordados, o Flexible JobShop Scheduling Problem com Flexibilidade de sequenciamento e o Flowshop Scheduling Problem com tempos de espera e permutação de sequência. Para ambos, inicialmente um algoritmo list scheduling (LS) que explora características do problema é desenvolvido e então estendido para um método do tipo Beam Search (BS) que utiliza o LS em seus principais elementos: (1) expansão dos níveis, (2) avaliação local dos candidatos e (3) avaliação global dos candidatos. Todos os métodos propostos são determinísticos e seus pseudocódigos são cuidadosamente descritos para garantir a replicabilidade dos resultados reportados. O desempenho dos métodos propostos são avaliados utilizando instâncias e outros métodos heurísticos da literatura. Os resultados computacionais obtidos mostram a eficiência das heurísticas propostas que superaram os métodos da literatura utilizando pouco tempo computacional. / In this thesis two diferent scheduling problems were addressed, the Flexible Job Shop Scheduling Problem with sequence Flexibility and the Flowshop Scheduling Problem with waiting times and sequence permutation. For both problems, firstly, a list scheduling (LS) algorithm which exploit features of the problem was developed and then it was extedend to a Beam Search (BS) method which use the LS in his main features: (1) level expansion, (2) local evaluation and (3) global evaluation. All the proposed methods are deterministics and their pseudocodes are carefully described to ensure the replicability of the reported results. The performance of the proposed methods was evaluated using instances and other heuristic methods found in literature. The computational results show the eficiency of the proposed heuristics, which outperformed the literature methods while using low computational time.

No description available.

現今企業在面臨市場需求快速變化、接單多樣化，及交貨期短的多重壓力下， 無不致力於改善作業流程以求獲利極大化，尤其是現場生產排程規劃一直是相當複雜而難以管理的部分。現行的軟體例如：企業資源規劃(ERP)、供應鏈管理(SCM)，即是希望藉由資訊科技以解決複雜的生產排程問題。 然而，大部分企業在使用這些系統時都發現，由於缺乏有效的現場管制功能(Shop Floor Control)，使得這些系統的效能受到很大的限制，而目前大多數的現場排程問題為零工式生產問題(Job Shop Problem)。 過去在零工式生產問題的理論上雖有許多傑出的研究，但研究與現場實際的問題之間有許多差異。其中最大的差異在於過去研究所使用的零工式生產問題假設所有的工作會以不同的流程經過所有的機器，然而在現場實際的零工式生產問題中卻顯示每一機器所處理的工作數目變異非常大。現場零工式生產生產排程問題包括兩個主要特性：1、每一工件可以擁有不等之操作數目；2、事先知道某些機器為瓶頸機器。本研究分別針對此兩個特性設計實驗一：產生工件擁有’等操作數’與’不等操作數’的問題；與實驗二：’無瓶頸機器’與’有瓶頸機器’的問題。在實驗中，我們以三個因素：工件數、機器數、和操作時間變異，模擬產生18種不同的狀況。然後以7種評量準則比較50個常用的派工法則在不同狀況下的表現。 研究結果發現，在實驗一與實驗二中，理論與實際現場排程問題在派工法則的表現上確實有極大的差異。本研究將這些其差異加以分析，並嘗試整理出一些規則以提供現場的使用者在面對不同狀況下選擇適當之派工法則的依據。我們相信本研究的成果不論對理論研究者、現場工程師、或生管軟體系統開發者都有極大價值。

Dans ce mémoire, nous étudions les méthodes itératives de recherche dans le cadre de la résolution du problème d'ordonnancement de type jobshop<br /><br />Plus que les performances en elles-mêmes, nous nous intéressons tout particulièrement à la compréhension du fonctionnement des méthodes de résolution ainsi qu'à l'analyse de l'influence de la coopération de plusieurs méthodes de recherche sur la qualité des solutions engendrées.<br /> <br />Dans un premier temps, nous évaluons l'apport de critères secondaires intégrés dans la fonction coût. Nous utilisons des algorithmes itératifs de recherche pour étudier l'impact de l'intégration de ces critères sur le paysage adaptatif ainsi que sur la qualité des ordonnancements engendrés.<br /><br />Nous proposons ensuite quelques améliorations du schéma d'application des opérateurs dans les algorithmes génétiques. <br /><br />Finalement, nous étudions quelques modèles d'hybridation des méta-heuristiques basés sur la recherche tabou et les algorithmes évolutifs.