Title page for ETD etd-4621112149731401

Type of Document

Master's Thesis

Author

Prakash, Divya

URN

etd-4621112149731401

Title

Bi-criteria Scheduling Problems on Parallel Machines

Degree

Master of Science

Department

Industrial and Systems Engineering

Advisory Committee

Advisor Name	Title
Kobza, John E.
Sarin, Subhash C.
Sherali, Hanif D.

Keywords

none

Date of Defense

1995-07-20

Availability

unrestricted

Abstract

Mathematical programming has not been used

extensively for the solution of scheduling problems.

Moreover, the study of bicriteria problems on single

and parallel machines is an open field for research.

This thesis is aimed at developing algorithms to solve

bicriteria problems more efficiently and in reasonable

amount of time and with little compromise on the

optimality of the solutions obtained. Two classes of

problems are considered. The first class consists of

scheduling unit duration tasks on parallel machines.

Various combinations of primary and secondary

criteria are considered and optimal seeking

algorithms of polynomial time complexity are

developed. The second class of problems assume

general processing time tasks. An algorithm is

developed for the primary criterion of total tardiness

and the secondary criterion of total flow time. This

algorithm is based on the solution of the underlying

mathematical program and makes use of dominance

relationship among the jobs and fixing of variables.

Experimental results are presented regarding its

performance.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	edt.pdf	203.13 Kb	00:00:56	00:00:29	00:00:25	00:00:12	00:00:01
	etd.pdf	203.13 Kb	00:00:56	00:00:29	00:00:25	00:00:12	00:00:01