The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Order scheduling in dedicated and flexible machine environments
Author:	Li, Haibing
View Online:	njit-etd2005-077 (xiv, 197 pages ~ 7.7 MB pdf)
Department:	Department of Computer Science
Degree:	Doctor of Philosophy
Program:	Computer Science
Document Type:	Dissertation
Advisory Committee:	Leung, Joseph Y-T. (Committee chair) Pinedo, Michael (Committee member) Gerbessiotis, Alexandros V. (Committee member) Liu, Chengjun (Committee member) Nakayama, Marvin K. (Committee member)
Date:	2005-05
Keywords:	Order scheduling Approximation algorithms Optimization NP-Hard Heuristics
Availability:	Unrestricted
Abstract:	Order scheduling models are relatively new in the field of scheduling. Consider a facility with m parallel machines that can process k different products (job types). Each machine can process a given subset of different product types. There are n orders from n different clients. Each order requests specific quantities of the various different products that can be produced concurrently on their given subsets of machines; it may have a release date, a weight and a due date. Preemptions may be allowed. An order can not be shipped until the processing of all the products for the order has been completed. Thus, the finish time of an order is the time when the last job of the order has been completed. Even though the idea is somewhat new that order scheduling measures the overall completion time of a set of jobs (i.e., an order requesting different product types) instead of the individual completion time of each product type for any given order, many applications require that decision-makers consider orders rather than the individual product types in orders. Research into order scheduling models is motivated by their various real-life applications in manufacturing systems, equipment maintenance, computing systems, and other industrial contexts, where the components of each order can be processed concurrently on the parallel machines. In this research, two cases of order scheduling models are studied, namely, the fully dedicated environment in which each machine can produce one and only one product type, and the fully flexible machine environment in which each machine can produce all product types. With different side constraints and objective functions, the two cases include a lot of problems that are of interest. Special interest is focused on the minimization of the total weighted completion time, the number of late orders, the maximum lateness, and so on. On the one hand, polynomial time algorithms are proposed for some problems. One the other hand, for problems that are NP-hard, complexity proofs are shown and heuristics with their worst-case performance and empirical analyses are also presented.