Bicriteria optimization of schedules on one and two machines

The practical applications of scheduling generally involve the optimization of more than one criterion. This thesis focuses on the bicriteria optimization problem of scheduling jobs on single and two machines. The optimization criteria that are considered are those of minimization of maximum tardiness and minimization of the total number of tardy jobs in the schedule. The former is considered as the primary criterion while the latter is considered as the secondary criterion. For the single machine problem, a search tree method is presented which is based on the implementation of some new dominance rules. Computational results presented show that the performance of this algorithm is better than that of an earlier work reported in the literature. For the two machine problem, a heuristic algorithm is developed to minimize maximum tardiness. Computational results are presented regarding the performance of this heuristic. A search tree method is developed for the optimization of the secondary criterion. This search tree method is similar to that for the single machine problem except that it does not use the dominance rules that were developed for the single machine case. Computational experience is presented for this algorithm.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Industrial Engineering and Operations Research

Department dc:contributor.department

Industrial Engineering and Operations Research

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1988

Author dc:creator

• Hariharan, Rema

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10919/80042

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/80042