Some blog feeds related to research interests can be found here.
Scheduling is a decision-making process that concerns the allocation of limited resources to a set of tasks with the view of optimizing one or more objectives. In today’s world of global competition, effective scheduling becomes imperative in order to meet customer requirements as quick as possible while maximizing the profits. Scheduling in manufacturing systems typically is associated with scheduling a set of jobs on a set of machines in order to maximize the throughput. In this work, we focus on one specific category of manufacturing system viz. cyclic permutation flow-shop where a set of jobs are repeatedly processed on all the machines in the same order and the direction of job-flow is unidirectional. Permutation flow-shop sequencing problem is a known NP-hard problem. Since it is computationally prohibitively expensive to obtain the optimal solution to the problem, researchers in this area have focused on developing heuristics to obtain near-optimal solutions.
I developed a simple but powerful mathematical representation to model flowshops based on max-plus algebraic formulism. Using the standard techniques available in max-plus algebra, the period of the modeled flowshop for a given sequence is obtained in O(m3p) complexity. We developed a construction algorithm on the lines of the NEH heuristic using the max-plus formulism. We observed that this construction heuristic yielded results similar if not better to that of NEH heuristic with lesser computational expense.
I also developed an efficient improvement algorithm that explores an extensive search space to ascertain the near-optimal solution with a worst-case complexity of O(m3p + m2p). We explored different perturbation mechanisms in order to transition from one sequence to another in the search space. Based on our in-depth experimentation and analysis, we concluded that a perturbation mechanism, where the better of the two procedures viz. swap and insertion is chosen, yields the best results. In addition, as result of our comparative analysis of some of the existing improvement heuristics (albeit not specifically for cyclic systems which has unfortunately not received much attention among researchers), we observed that the performance of the improvement heuristics based on max-plus formulism was dramatically better than most of the other existing improvement heuristics.
An efficient and effective data exchange mechanism is indispensable for multi-disciplinary optimization frameworks that provide a common working environment to increase interdisciplinary interactions and reduces the design cycle time. Some of the existing data exchange mechanisms have been studied and a new data exchange mechanism has been implemented. The scope of this work has been to develop two tools namely the Vector tool and the Name-Value tool to handle data in the form of one-dimensional arrays and name-value pairs respectively. A data caching algorithm has also been implemented so that the two tools interoperate with the help of adapters that translate data across the two formats.
Last updated on August 17, 2009
This document was translated from LATEX by HEVEA.