Job shop scheduling to minimize makespan with explicit material handling considerations
Pandit, Ram
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/22207
Description
Title
Job shop scheduling to minimize makespan with explicit material handling considerations
Author(s)
Pandit, Ram
Issue Date
1990
Doctoral Committee Chair(s)
Palekar, Udatta S.
Department of Study
Mechanical Science and Engineering
Discipline
Mechanical Science and Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Industrial
Operations Research
Language
eng
Abstract
The efficient operation of a Flexible Manufacturing System (FMS) can be achieved by exploiting (i) Routing Flexibility and (ii) Scheduling Flexibility. Routing flexibility allows the selection of a machine on which an operation should be performed. Scheduling flexibility allows the determination of the processing sequence of jobs on a machine. Typically, the sequence of machines that a job has to visit is fixed and efficiencies can only be obtained by appropriate selection of machine schedules. The resulting problem requires sequencing of jobs on machines and the determination of routes for material handling vehicles. Traditionally, the machine sequences are determined independent of the vehicle routes. We demonstrate that, such a sequential approach often leads to suboptimal schedules. We study the problem of simultaneous scheduling of both the machines and the material handling system.
The difficulty of the simultaneous scheduling problem depends on the physical attributes of the FMS such as buffer sizes, travel distances, number of vehicles and their capacities. We present a classification scheme to categorize problems based on their physical attributes. We also show that the general problem is NP-Complete. Exact solution procedures for the problem must therefore be enumerative in nature. We present a binary integer linear programming formulation for the problem. We discuss the mathematical structure of the problem and show that there are two major sub-problems (i) A classical job-shop problem; and (ii) Routing of material handling vehicles. In the case of a single material handling vehicle, the second problem may be represented as an asymmetric traveling salesman problem with precedences and ready times (ATSP-PCRT). This variant of the ATSP has not thus far been addressed in literature. We develop a branch-and-bound procedure for its solution.
The overall problem is also solved exactly using a branch-and-bound approach. Because of the extreme difficulty of the problem exact solutions are obtained only for small problems (up to 3 machines and 6 jobs). For larger problems, we develop four heuristics. The first heuristic uses a sequential approach to scheduling of machines and the material handling system. The remaining three heuristics use a shifting bottleneck approach and differ in the treatment of the material handling vehicle. Both the exact procedure and the heuristics are extensively tested using randomly generated problems. Results of this computational testing are reported and discussed.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
