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

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.

No description available.

An analysis tableau suitable for investigating flow-shop attributes is presented in detail 1. Geometric properties, inherent within the tableau, are employed using graph theory concepts in developing a heuristic algorithm for makespan minimization. Computer implementation of this algorithm revealed promising results when compared with several state of-the-art heuristic algorithms. The tableau can be conceived as a three-dimensional matrix with the first two indices consisting of job numbers (rows) and machine numbers (columns). The third index is used to distinguish processing times and accumulative makespan values. The matrix is as informative as the Gantt Chart and yet offers additional advantages when considering the flow-shop problem, such as: 1. Provides an instructional tableau format which is organized, systematic, and directly amenable for hand or digital-computer calculations, 2. Depicts computational contingencies for accumulative makespan values (individual job due-dates as well as flow-shop makespan), 3. Depicts machine and job dominances, 4. Allows for sensitivity analysis {effects of processing times upon accumulative makespan values), 5. Identifies critical-processing times, 6. Reveals where external improvements would be cost effective, 7. Representation is easily modified for job permutations, 8. Representation is not limited to small flow-shops (low number of jobs and/or machines), 9. Allows for additional insight when investigating heuristics, and 10. Can be used as an instructional- , managerial- , and/or a research- tool for analyzing flow-shop attributes. The tableau allows a macro-sensitivity analysis of the entire flow-shop. Specifically, the maximum increase in various processing times, without increasing the flow-shop make span, can be determined. This analysis utilizes graphical representations (segments and nodes) in matrix (tableau). Graphical representation is a convenient means for preserving the history of how each accumulative makespan value was mathematically generated. Concepts such as: partial-paths and critical-paths in conjunction with regions-of-influence are discussed in order to determine the interrelationship between the accumulative makespan values and the processing times, for a specific job sequence. / M. S.

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.