Identical Parallel Machine Scheduling with Machine Availability and Eligibility Constraints to Minimize Total Completion Time
| Autor: | Yu-Cyuan Chen, 陳昱全 |
|---|---|
| Rok vydání: | 2016 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 104 In most scheduling problem, machines are always continuously available to process jobs all the time. However, it usually exist unavailable time intervals for routine maintenance in practice. Besides, some job is suitable for specific machines to process based on the property of job. In this study, we consider the problem of scheduling n non-preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time. For the scheduling problem, we use branch and bound method to find the optimal solution. In the branch and bound algorithm, we discuss two way of branching. First one is, we adopted the branching scheme from Mellouli et al. (2009) which concept is through assigning an additional job on each available interval. We also propose the other approach of branching which contained the concept of forward scheduling. Based on the branching scheme we proposed, we also propose a dominance rule to eliminate redundant nodes. We adopted the property in Yalaoui and Chu (2006) which could solve the reduced problem by relaxing the restriction of machine eligibility constraint and allow jobs split, and let the optimal solution to be our lower bound. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|