tailieunhanh - A heuristic hybrid framework for vector job scheduling

We examine the first phase of a known NP-hard 2-stage assembly problem. It consists of sequencing a set of jobs having multiple components to be processed. Each job has to be worked on independently on a specific machine. We consider these jobs to form a vector of tasks. Our objective is to schedule jobs on the particular machines in order to minimize the completion time before the second stage starts. | Yugoslav Journal of Operations Research 27 (2017), Number , 31–45 DOI: A HEURISTIC HYBRID FRAMEWORK FOR VECTOR JOB SCHEDULING Nareyus I Lawrance AMALDASS Brunel University, London, UK nareyus22@ Cormac LUCAS Brunel University, London, UK Nenad MLADENOVIC LAMIH, University of Valenciennes, France and Mathematical Institute, SANU, Belgrade, Serbia Received: April 2015 / Accepted: July 2016 Abstract: We examine the first phase of a known NP-hard 2-stage assembly problem. It consists of sequencing a set of jobs having multiple components to be processed. Each job has to be worked on independently on a specific machine. We consider these jobs to form a vector of tasks. Our objective is to schedule jobs on the particular machines in order to minimize the completion time before the second stage starts. We first develop a new mathematical programming formulation of the problem and test it on a small problem instance using an integer programming solver. Then, we develop a heuristic algorithm based on Ant Colony Optimization and Variable Neighborhood Search metaheuristics in order to minimize the total completion time. The performance of our implementation appears to be efficient and effective. Keywords: Variable Neighborhood Search, Ant Colony Optimization, Scheduling, Integer Programming. MSC: 90B06, 90C05, 90C08. 32 Amaldass, , / Heuristic Hybrid Framework 1. INTRODUCTION The focus of this paper is on solving separately the first stage of the two stage assembly scheduling problems [2, 3] which various industries are faced with. For instance, consider the computer hardware industry. Computers are produced by assembling various components depending on customer specifications. These components are monitors, hard disks, CD/DVD ROM’s, keyboards, mouse etc. Each components, having its own specifications, is made separately on an adequate machine. As .