Content area
Full Text
Abstract
In this paper, a novel mixed integer linear programming formulation is developed for the Flexible Job Shop Scheduling Problem. The theoretical foundation of the proposed MILP model takes its root from the sequence-based modeling paradigm for production scheduling, which was initially propounded by Alan. S. Manne. The proposed MILP model is capable of solving scheduling problems associated with both totally- and partially-flexible job shops. The developed MILP model consists of fewer numbers of continuous variables and is capable of solving larger size instances of the problem. In order to demonstrate the effectiveness of the model, it is applied to standard benchmarks from literature. In order to investigate the combined impact of possessing fewer numbers of continuous decision variables on the performance of the proposed MILP model, three other different performance measures: computational time, size dimensionality and quality of generated schedules are utilized. Finally, the proposed MILP is compared vis-à-vis the best-performing MILP in the literature. The obtained results simply corroborate the superiority of our developed MILP model in all the aforementioned performance measures.
Keywords
Production Scheduling, Flexible Job Shops, Mixed Integer Linear Programming
(ProQuest: ... denotes formulae omitted.)
1. Introduction
Over the last 6 decades, effective production scheduling mechanisms have proven to be increasing productivity and machine utilization. Algorithmic and scientific production scheduling came to existence once the first production scheduling heuristic technique was proposed by Johnson [1]. Soon after the proposal of the first scheduling technique and increased popularity and recognition of operations research in industrial society, developments of the first mathematical models to solve scheduling problems were triggered. Mathematical models ranging from pure integer programming formulations to highly non-linear mixed integer programming models have always been indispensable concomitant of tackling production scheduling problems. Due to the imbalance between the advancements in mathematical modeling and related software, mathematical programming has mostly been regarded as a surrogate solution methodology as prohibitive computational burden is usually associated. With advances in computing and advent of multiprocessors, developments of mathematical models regained unprecedented momentum.
As a solution methodology, it is used to thoroughly characterize the shop floor and solve the scheduling problems for small-to-medium sized problems. The more efficient mathematical models are, the larger the size of the problem that can be tackled in reasonable amount...