Minimum cost scheduling of resource constrained jobs on parallel machines under control of interchangeable processors Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/pg15bh42s

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • A special case of a parallel multiprocessor scheduling (MP) problem is investigated. A set of jobs with a known process time and a.resource requirement is scheduled on machines controlled by processors,and the total changeover cost between jobs is to be minimized. Each processor may control up to two machines and requires a unit of a type of resource. A job may be processed by the machine provided that the processor is equipped with the appropriate type of resource to handle the job. The changeover cost is the sum of the job grade switching cost and of the resource brand switching cost. Three heuristic algorithms are developed to solve the MP problem. The first algorithm uses the "minimum cost rule" applied to the machine with the shortest current makespan with an adaptation of the "longest processing time" algorithm with the consideration of resource allocation. The second algorithm includes a planning horizon and assigns jobs to machines based upon the least changeover cost until the planning horizon is exceeded for the machine. The third algorithm is based upon a generalized formulation of the traveling salesman problem with more than one salesman. It is a bin-packing branch-and-bound algorithm using the first-fit-decreasing method to minimize the makespan. FORTRAN programs are developed and used to process actual industrial data from an aluminum reduction plant. With 13 to 26 jobs of 8 to 16 types, 6 to 8 resource types, 3 processors and 6 machines, the savings in total changeover cost using the best algorithm ranged from 14% to 51% of the cost resulting from the manual scheduling that was actually used. In dollars, the 51% reduction corresponded to about $23,000 for that one schedule.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-09-17T19:09:25Z (GMT) No. of bitstreams: 1 NgGeorgeKwokWing1981.pdf: 1849352 bytes, checksum: 5ac9c510449808c4cfbb6498ab1a1def (MD5)
  • description.provenance : Submitted by Kirsten Clark (kcscannerosu@gmail.com) on 2013-08-28T23:33:46Z No. of bitstreams: 1 NgGeorgeKwokWing1981.pdf: 1849352 bytes, checksum: 5ac9c510449808c4cfbb6498ab1a1def (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-08-30T20:43:00Z (GMT) No. of bitstreams: 1 NgGeorgeKwokWing1981.pdf: 1849352 bytes, checksum: 5ac9c510449808c4cfbb6498ab1a1def (MD5)
  • description.provenance : Made available in DSpace on 2013-09-17T19:09:25Z (GMT). No. of bitstreams: 1 NgGeorgeKwokWing1981.pdf: 1849352 bytes, checksum: 5ac9c510449808c4cfbb6498ab1a1def (MD5) Previous issue date: 1980-12-18

Relationships

In Administrative Set:
Last modified: 08/07/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items