• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

數個瓶頸為基礎的啟發式法則求解彈性流程系統排程問題 / BOTTLENECK-BASED HEURISTICS FOR FLEXIBLE FLOW LINE SCHEDULING PROBLEMS WITH A BOTTLENECK STAGE

陳俊龍, Chen,Chun Lung Unknown Date (has links)
In this research, we study flexible flow line scheduling problems with unrelated parallel machines and with a bottleneck stage. The measures of performances are to minimize makespan, to minimize the number of tardy jobs, and to minimize total tardiness, considered respectively. Several bottleneck-based heuristics are developed to solve these scheduling problems. A bottleneck-driven multiple insertion heuristic (BDMIH) is proposed to solve problems with makespan as the objective. The essential idea of BDMIH is that we think the scheduling of jobs at the bottleneck stage may affect the performance of a heuristic for scheduling jobs in all stages. Therefore, in this heuristic we let jobs entering the sequence at the first stage be driven by their sequence entering at the bottleneck stage. Given an FFL problem with a bottleneck stage, this heuristic first identifies the bottleneck stage, then generates an initial sequence of jobs by a variant of Johnson’s rule (SPT-LPT rule), and finally applies a multiple insertion heuristic to find the best schedule. Another heuristic, a bottleneck-based due-date decision heuristic (BBDDDH), is developed to solve problems with the number of tardy jobs as the objective. The heuristic consists of three steps: (1) Identifying the bottleneck stage, (2) Scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage, and (3) Using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule jobs at bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at bottleneck stage. The last bottleneck-based heuristic, a bottleneck-driven adaptable multiple insertion heuristic (BDAMIH), is constructed to solve problems with total tardiness as the objective. The main idea of BDAMIH is combined with the ideas of BDMIH and BBDDDH. The main difference between BDAMIH and BDMIH is that BDMIH generates an initial sequence of jobs before performing the insertion heuristic; however, BDAMIH is adaptable to select a job within the process of the insertion heuristic. To evaluate the performance of the proposed heuristics, several well-known dispatching rules and heuristics are investigated for comparison purposes and computational experiments are performed on randomly generated test problems. Computational results show that the proposed heuristics significantly outperform all well-known dispatching rules or heuristics. Also, an analysis of the experimental factors is performed, and several interesting insights of the proposed heuristics are discovered.

Page generated in 0.0233 seconds