Parallel flow shop schedulİng wİth common workstatİons

Download
2019
Çakıcı, Muhammet Kemal
In this thesis, we address the parallel flow shop scheduling problem with common workstations to minimize the makespan, considering the flow shop design defined solely by the number of operators at the workstations. We are motivated by the production environment of a compressor manufacturing company located in Konya, Turkey. Different from the similar studies in the literature, we use common workstations at some of the stages, prefer to place limited buffer areas between the stages, and do not allow for job crossing between the flow shops. We develop two different Mixed Integer Linear Programming (MILP) models for this scheduling problem. These MILPs barely provide the optimal solution in almost one-hour time which is the time restriction in this study; hence, we propose several heuristic approaches that are based on the well-known NEH Algorithm. Moreover, two dispatching rules, SPT and LPT, are utilized to evaluate the results of the MILPs and the proposed heuristics better. We perform extensive computational experiments using several problem instances that are differentiated by the number of operators and jobs, and compare the solution approaches. The results indicate that the proposed heuristic approaches are superior to the dispatching rules providing very close results to the MILP results in a short time and even better results as the number of jobs increases. In the experiments carried out for the compressor company’s case, the proposed heuristic methods provide promising solutions that make it possible for the decision maker to select the most productive shop design doubling the production volume.

Suggestions

Scheduling a batch processing machine with non-identical job sizes
Azizoğlu, Meral (2000-07-10)
The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with arbitrary job processing times, job weights and job sizes. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to similar to 25 jobs in reasonable C...
Preemptive scheduling on identical parallel machines subject to deadlines
Azizoğlu, Meral (2003-07-01)
We consider the problem of scheduling n preemptive jobs with deadlines on in identical parallel machines so as to minimize total completion time. We show that the problem is polynomially solvable when the processing times and deadlines are agreeable.
On the minimization of total weighted flow time with identical and uniform parallel machines
Azizoğlu, Meral (1999-02-16)
We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances.
Scheduling a batch processing machine with incompatible job families
Azizoğlu, Meral (2001-04-01)
The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with incompatible job families. Jobs in a given family have identical job processing times, arbitrary job weights, and arbitrary job sizes. Batches are limited to jobs from the same family. The scheduling objective is to minimize total weighted...
Using genetic algorithms for single-machine bicriteria scheduling problems
Köksalan, Mustafa Murat; Keha, AB (2003-03-16)
We consider two bicriteria scheduling problems on a single machine: minimizing flowtime and number of tardy jobs, and minimizing flowtime and maximum earliness. Both problems are known to be NP-hard. For the first problem, we developed a heuristic that produces an approximately efficient solution (AES) for each possible value the number of tardy jobs can take over the set of efficient solutions. We developed a genetic algorithm (GA) that further improves the AESs. We then adapted the GA for the second probl...
Citation Formats
M. K. Çakıcı, “Parallel flow shop schedulİng wİth common workstatİons,” Thesis (M.S.) -- Graduate School of Natural and Applied Sciences. Industrial Engineering., Middle East Technical University, 2019.