Graduate Thesis Or Dissertation
 

A methodology for scheduling jobs in a flexible flowshop with sequence dependent setup times and machine skipping

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/0r9676338

Descriptions

Attribute NameValues
Creator
Abstract
  • A flexible flowshop, comprised of one or more stages having unrelated parallel machines, is investigated in this research. Unrelated parallel machines can perform the same function but have different capacity or capability. Since this problem is motivated by industry research, dynamic job release times and dynamic machine availability times have been considered. Each job considered in this research can have different weight and due date. Sequence-dependent setup times of jobs further add to the complexity of the research. Machine skipping is yet another innate feature of this research that allows jobs to skip one or more stages depending upon customer's demand or budgetary constraints. The objective of this research is to minimize the sum of the weighted tardiness of all jobs released within the planning horizon. The research problem is modeled as a mixed (binary) integer-linear programming model and is shown to be strictly NP-hard. Being strongly NP-hard, industry size problems cannot be solved using an implicit enumeration technique within a reasonable computation time. Cognizant of the challenges in solving industry-size problems, we use the tabu-search-based heuristic solution algorithm to find optimal/near optimal solutions. Five different initial solution finding mechanisms, based on dispatching rules, have been developed, to initiate the search. The five initial solution finding mechanisms (IS1-IS5) have been used in conjunction with the six tabu-search-based heuristics (TS1-TS6) to solve the problems in an effective and efficient manner. The applicability of the search algorithm on an example problem has been demonstrated. The tabu-search based heuristics are tested on seven small problems and the quality of their solutions is compared to the optimal solutions obtained by the branch-and-bound technique. The evaluations show that the tabu-search based heuristics are capable of obtaining solutions of good quality within a much shorter computation time. The best performer among these heuristics recorded a percentage deviation of only 2.19%. The performance of the tabu-search based heuristics is compared by conducting a statistical experiment that is based on a randomized complete block design. Three sizes of problem structures ranging from 9 jobs to 55 jobs are used in the experiment. The results of the experiment suggest that no IS finding mechanism or TS algorithm contributed to identifying a better quality solution (i.e a lower TWT) for all three problem instances (i.e. small, medium and large). In other words, no IS finding mechanism or TS algorithm could statistically outperform others. In absence of a distinct outperformer, TS1 with short-term memory and fixed TLS are recommended for all problem instances. When comparing the efficiency of the search algorithm, the results of the experiment show that IS1, which refers to the EDD (earliest due date) method, is recommended as the initial solution generation method for small problem sizes. The EDD method is capable of obtaining an initial solution that helps the tabu-search based heuristic to get to the final solution within a short time. TS1 is recommended as the tabu-search based heuristic for large problems, in order to save on time. TS1 is also recommended to solve small and medium problem structures in absence of a statistically proven outperformer.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details PandyaVaibhav2012.pdf 2017-08-08 Public Download