Exact algorithms for scheduling multiple families of jobs on parallel machines

Exact algorithms for scheduling multiple families of jobs on parallel machines

0.00 Avg rating0 Votes
Article ID: iaor20042066
Country: United States
Volume: 50
Issue: 10
Start Page Number: 823
End Page Number: 890
Publication Date: Oct 2003
Journal: Naval Research Logistics
Authors: ,
Keywords: combinatorial analysis, programming: branch and bound
Abstract:

In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job ofone family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time.

Reviews

Required fields are marked *. Your email address will not be published.