<p>This thesis describes efficient algorithms and complexity results for some machine scheduling and related problems, which are encountered in automated manufacturing systems. We introduce a new class of robotic-cell scheduling models. The novel aspect is that parts need to reenter machines several times before they are finished. The problem is to find the sequence of robot move cycles and the part processing sequence that jointly minimize the cycle time or the makespan. We show that the problems are computationally intractable with three machines and present polynomial solutions for a variety of two-machine configurations. We then consider the problem of scheduling multi-component parts in a two-machine robotic cell, where each part is composed of K identical components to be processed together on the first machine, then processed on the second machine individually. We study the cycle time and makespan minimization problems, and show that both are polynomially solvable. We investigate the problem of minimizing cycle time in a two-machine job shop, where each job has at most three operations. We reduce the problem to a two-machine reentrant flow shop problem. By extending previous results on the reentrant flow shop problem, we propose a new pseudo-polynomial algorithm, as well as a fully polynomial-time approximation scheme for certain special cases of the job shop problem. We also describe a 4/3-approximation algorithm for the general problem, and identify several well-solvable cases. Finally, we study special cases of the traveling salesman problem on permuted Monge matrices, which arose from robotic-cell scheduling problems. By using the theory of subtour patching, we reduce the problems to finding a minimum-b -weight spanning tree in the patching graph. In general, this problem is [Special characters omitted.] -hard. We show, however, that newly defined special properties of the distance matrix allow us to find in polynomial time a minimum-b -weight spanning tree, and thus an optimal tour, for these new classes.</p> / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/7464 |
| Date | 04 1900 |
| Creators | Xue, Zhihui |
| Contributors | Steiner, George, Management Science/Information Systems |
| Source Sets | McMaster University |
| Detected Language | English |
| Type | thesis |
Page generated in 0.0019 seconds