Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

A Bicriteria Simulated Annealing Algorithm for Scheduling Jobs on Parallel Machines with Sequence Dependent Setup Times

Persson, Rasmus (2008) In MSc Theses
Department of Automatic Control
Abstract
The study considers the scheduling problem of identical parallel machines subject to minimization of the maximum completion time and the maximum tardiness expressed in a linear convex objective function. The maximum completion time or makespan is the date when the last job to be completed leaves the system. The maximum tardiness is indicated by the job that is completed with the longest delay relative its due date. Minimizing both criteria can help assuring a high utilization of the production system as well as a high level of service towards the client. Due to the complexity of the problem, a Simulated Annealing (SA) heuristic has been implemented to be able to obtain an efficient solution in a reasonable running time. A set of n jobs is... (More)
The study considers the scheduling problem of identical parallel machines subject to minimization of the maximum completion time and the maximum tardiness expressed in a linear convex objective function. The maximum completion time or makespan is the date when the last job to be completed leaves the system. The maximum tardiness is indicated by the job that is completed with the longest delay relative its due date. Minimizing both criteria can help assuring a high utilization of the production system as well as a high level of service towards the client. Due to the complexity of the problem, a Simulated Annealing (SA) heuristic has been implemented to be able to obtain an efficient solution in a reasonable running time. A set of n jobs is assigned, to one of the m identical parallel machines. Each job is processed in only one operation before its completion after which it leaves the system. Constraints, such as due dates for each job and setup times for the machines, are considered. The resolution procedure consists of two phases and begins with an initial solution generator. Then a SA heuristic is applied for further improvement of the solution. 4 generators are used to create an initial solution and 3 to generate neighbour solutions. To test and verify the performance of the proposed resolution procedure, a computational experimentation has been realized on a set of test problems generated ad-hoc. (Less)
Please use this url to cite or link to this publication:
author
Persson, Rasmus
supervisor
organization
year
type
H3 - Professional qualifications (4 Years - )
subject
publication/series
MSc Theses
report number
TFRT-5821
ISSN
0280-5316
language
English
id
8847679
date added to LUP
2016-03-17 10:20:30
date last changed
2016-03-17 10:20:30
@misc{8847679,
  abstract     = {{The study considers the scheduling problem of identical parallel machines subject to minimization of the maximum completion time and the maximum tardiness expressed in a linear convex objective function. The maximum completion time or makespan is the date when the last job to be completed leaves the system. The maximum tardiness is indicated by the job that is completed with the longest delay relative its due date. Minimizing both criteria can help assuring a high utilization of the production system as well as a high level of service towards the client. Due to the complexity of the problem, a Simulated Annealing (SA) heuristic has been implemented to be able to obtain an efficient solution in a reasonable running time. A set of n jobs is assigned, to one of the m identical parallel machines. Each job is processed in only one operation before its completion after which it leaves the system. Constraints, such as due dates for each job and setup times for the machines, are considered. The resolution procedure consists of two phases and begins with an initial solution generator. Then a SA heuristic is applied for further improvement of the solution. 4 generators are used to create an initial solution and 3 to generate neighbour solutions. To test and verify the performance of the proposed resolution procedure, a computational experimentation has been realized on a set of test problems generated ad-hoc.}},
  author       = {{Persson, Rasmus}},
  issn         = {{0280-5316}},
  language     = {{eng}},
  note         = {{Student Paper}},
  series       = {{MSc Theses}},
  title        = {{A Bicriteria Simulated Annealing Algorithm for Scheduling Jobs on Parallel Machines with Sequence Dependent Setup Times}},
  year         = {{2008}},
}