No description available.

This report examines the widely acceptable Heuristic and Exact procedures for solving the problem of project scheduling and control under constrained resources. Heuristic approaches are more practical, however they depend on the type of the project as well as the resources involved. Exact procedures are illustrated using an Integer Linear Programming formulation of the problem, and also solving it using the Branch and Bound Technique. Impracticality of the exact methods stews from the fact that the computations expand to an unmanageable amount.

Traditional critical path methods imply the assumption of unlimited availability of resources. Mathematical models and heuristic techniques are two alternatives that consider resource limitation to sequence the activities of a project. This research explores the consideration of project scheduling under resource constraints for the specific case of single resource, single project scheduling. A computer model called GENRES-II search model is developed using a modification of Brooks' algorithm to develop project schedules. The criteria used are various weighted combinations of ACTIM, ACTRES and ACTFOL. An improvement of GENRES-II solutions is obtained when the best set of GEN-II values is input to a computer model called COMSOAL simulation model. The criteria developed generates a large number of feasible solutions rapidly. The probability of generating optimal solutions is related to the size of the generated sample. Eight network cases were considered to validate both computer models. Special attention was given to those activities that were considered critical at a specific time. The number of resources available was increased to a new higher limit in order to schedule activities that became critical. The GENRES-II model was effective in finding project durations equal to or less than ACTIM, ACTRES, GENRES or ACTFOL. The COMSOAL model was found very effective in most of the cases in improving the GEN-II solutions.

Research in job shop scheduling has concentrated on sequencing simple, single component jobs that require no coordination of multiple parts for assembly. However, since most jobs in reality involve some assembly work, scheduling multiple component jobs through an assembly shop, where both serial and parallel operations take place, represents a more realistic and practical problem. The scheduling environment for multiple component jobs in terms of routing, sequencing, and the pacing of common components may be quite complex, and, as such, requires special scheduling considerations. The purpose of this research is to evaluate scheduling policies for the production of assembled products in a job shop environment, termed "assembly shop". The specific scheduling policies examined include duedate assignment procedures, labor assignment procedures, and item sequencing rules. The sensitivity of these policies to product structure is also addressed. / Ph. D.

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. / Master of Science

M. S.

In this thesis we present new results for the makespan and the flowtime in a flow shop without intermediate storage between machines. We consider m machines and n jobs with random processing times. Since there is no intermediate storage between machines, a job which has finished processing at one machine may have to stay at that machine until the next machine is free. This phenomenon is known as blocking. Our goal is to select the optimal schedule; in our case, the schedule which in some sense minimizes the makespan or the flowtime. Makespan is the total time required to process a set of jobs and flowtime is sum of all the times at which jobs are completed. Our results require various stochastic orderings on the processing time distributions. Some of these orderings minimize the expected flowtime or expected makespan, and some stochastically minimize the makespan. The stochastic minimization results are much stronger. The optimum sequence in these cases not only minimize the expected makespan, but also maximize the probability of completing a set of jobs by time t for any t. Our last result resolves the conjecture of Pinedo (1982a) that in a stochastic flow shop with m machines, n-2 deterministic jobs with unit processing time, and two stochastic jobs each with mean one, the sequence which minimizes the expected makespan has one of the stochastic jobs first and the other last. We prove that Pinedo's conjecture is almost true. We prove that either the sequence suggested by Pinedo or a sequence in which the stochastic jobs are adjacent at one end of the sequence minimizes the expected makespan. Our result does not require the stochastic jobs to have an expected value of one. Furthermore, we show that our result cannot be improved in the sense that in some cases one sequence is strictly optimal and in other cases the other is strictly optimal. / Master of Science

No description available.

The focuses of this dissertation are problems of batch production scheduling problems for perishable products with setup times, with the main applications in answering production planning problems faced by manufacturers of perishable products, such as beers, vaccines and yoghurts. The benefits of effective production plans can help companies reduce their total costs substantially to gain the competitive advantages without reduction of the service level in a globalize economy. We develop concepts and methodologies that are applied in two fundamental problems: (i) the batch production scheduling problem for perishable products with sequence-independent setup times (BPP-SI) and (ii) the batch production scheduling problem for perishable products with sequence-dependent setup times (BPP-SD). The problem is that given a set of forecast demand for perishables products to be produced by a set of parallel machines in the single stage of batch production, with each product having fixed shelf-life times and each machine requiring setup times before producing a batch of product, find the master production schedule which minimizes total cost over a specified time horizon. We present the new models for both problems by formulating them as a Mixed Integer Program (MIP) on the discrete time. Computational studies in BPP-SI and BPP-SD for industrial problems are presented. In order to efficiently solve the large BPP-SI problems in practice, we develop the five efficient heuristics. The extensive computational results show that the developed heuristics can obtain the good solution for the very large problem size and require very short amount of computational time.

A new implementation of the calendar queue is described in this thesis. The calendar queue as previously implemented depended upon the use of multiple linked lists for the control of queue discipline. In the calendar heap implementation, the heap has been used to replace the previous functions of the linked list. Testing of the claim of O(1) execution time for the calendar queue was done. Comparisons of execution times of the calendar queue and the calendar heap have been made. Descriptions of the implementation as well as the complete C code for the calendar heap are included.