Back to search

McMaster University

Shop scheduling in manufacturing systems: Algorithms and complexity

Abstract

dc:description.abstract

<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>

Degree

thesis:*
Department dc:contributor.department
Management Science/Information Systems
Year dc:date.issued
2004

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Xue, Zhihui
Advisor dc:contributor.advisor
  • Steiner, George

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/2741
3835
1411177

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Xue, Zhihui. Shop scheduling in manufacturing systems: Algorithms and complexity. 2004. http://hdl.handle.net/11375/7464