Metaheuristic Solutions to the Response Time Variability Problem

Abstract

The problem of variation in the response time is known as response time variability problem (RTVP). RTVP is a combinatorial NP-hard problem which has a broad range of real-life applications: mixed-model assembly line in production systems, multi-threaded computer systems, network environments, broadcast of commercial video tapes, salesman's routes, and machine maintenance, among others. The RTVP arises whenever events, jobs, clients or products need to be sequenced so as to minimize the variability of the time they wait for their next turn in obtaining the resources they need to advance. The concept of variation in response time has been recently appeared in literature and a lot of research is being carried out in this areas.

This dissertation includes recent researches regarding the response time variability problem. Our concern in this dissertation is to find out near optimal sequence of jobs with objective of minimizing the response time variability. Several solutions based on heuristics and metaheuristics exist in the literature to fulfill this objective. This dissertation work focuses on the metaheuristic solutions to the RTVP. The metaheuristic procedure to solve the RTVP is put forward by applying the following three procedures: Multi-Start (MS), Greedy Randomized Adaptive Search Procedure (GRASP) and practical swarm optimization (PSO). This dissertation work mainly focused on multi-start and GRASP. In this dissertation, we implement and analyze the experimental result of the metaheuristic algorithms.