東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Three essays in parallel machine sch...

Case Western Reserve University.

Linked to FindBook

Google Book

Amazon

博客來

Three essays in parallel machine scheduling.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Three essays in parallel machine scheduling./
Author:	Garg, Amit.
Description:	115 p.
Notes:	Adviser: A. Dale Flowers.
Contained By:	Dissertation Abstracts International68-10B.
Subject:	Engineering, Industrial. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoeng/servlet/advanced?query=3286205
ISBN:	9780549291053

Three essays in parallel machine scheduling.
Garg, Amit.

Three essays in parallel machine scheduling. - 115 p.

Adviser: A. Dale Flowers.

Thesis (Ph.D.)--Case Western Reserve University, 2008.

This research consists of three essays in parallel machine scheduling. The first two essays focus on the parallel multipurpose machine scheduling problem, while the last focuses on the parallel identical machine scheduling problem. In the first essay, a branch and bound procedure for assigning jobs to parallel multipurpose machines is developed and tested. Multipurpose machines can process some of the jobs, but not necessarily all of them. All the machines that can process a particular job require the same amount of time to complete it. This algorithm uses the particular structure of the multipurpose machine problem to improve the lower and upper bound at any node rather than solving the linear programming relaxation problem at every node. This enables the algorithm to outperform the prior algorithm written to solve the parallel multipurpose machine problem.

ISBN: 9780549291053Subjects--Topical Terms:

626639
Engineering, Industrial.

Three essays in parallel machine scheduling.
LDR:03414nam 2200289 a 45 001 856572
005 20100709
008 100709s2008 ||||||||||||||||| ||eng d
020 $a 9780549291053
035 $a (UMI)AAI3286205
035 $a AAI3286205
040 $a UMI $c UMI
100 1 $a Garg, Amit. $3 1023395
245 1 0 $a Three essays in parallel machine scheduling.
300 $a 115 p.
500 $a Adviser: A. Dale Flowers.
500 $a Source: Dissertation Abstracts International, Volume: 68-10, Section: B, page: 6887.
502 $a Thesis (Ph.D.)--Case Western Reserve University, 2008.
520 $a This research consists of three essays in parallel machine scheduling. The first two essays focus on the parallel multipurpose machine scheduling problem, while the last focuses on the parallel identical machine scheduling problem. In the first essay, a branch and bound procedure for assigning jobs to parallel multipurpose machines is developed and tested. Multipurpose machines can process some of the jobs, but not necessarily all of them. All the machines that can process a particular job require the same amount of time to complete it. This algorithm uses the particular structure of the multipurpose machine problem to improve the lower and upper bound at any node rather than solving the linear programming relaxation problem at every node. This enables the algorithm to outperform the prior algorithm written to solve the parallel multipurpose machine problem.
520 $a The second essay focuses on developing theoretical techniques to exploit the specific structure of the problem in order to gain greater efficiency. This is important if we are to solve more challenging problems occurring in real world scenarios. This essay has two sections. The first section focuses on decomposing the problem into smaller subproblems that can each be solved efficiently. In the second section, we develop multiple improved lower bounds for the problem, and also develop a heuristic that can be used when these lower bounds are superior to the linear programming relaxation lower bound. Under certain conditions, both the decomposition and the lower bounding techniques substantially reduce the computational time of the original branch and bound procedure, as well as the time required if we solve the problem with Integer Programming software.
520 $a In the third essay, we optimize a bi-criteria problem of minimizing a weighted function of the makespan and the cost of assigning jobs to the machines for the identical parallel machine problem. In this problem, each machine is able to process every job, and the amount of time required to complete the job is the same regardless of which machine processes it. The cost of assigning a job to the machine depends on the machine and the processing time of the job. We develop a procedure to estimate the lower and upper bound on the values of the makespan in the optimal solution. We also estimate the maximum number of machines with non-zero assignments in the optimal solution. By developing these problem specific constraints, the computation time of the integer programming software was substantially reduced.
590 $a School code: 0042.
650 4 $a Engineering, Industrial. $3 626639
690 $a 0546
710 2 $a Case Western Reserve University. $3 1017714
773 0 $t Dissertation Abstracts International $g 68-10B.
790 $a 0042
790 1 0 $a Flowers, A. Dale, $e advisor
791 $a Ph.D.
792 $a 2008
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoeng/servlet/advanced?query=3286205