Multi-objective Algorithms for the Single Machine Scheduling Problem with Sequence-Dependent Family Setups

This work treats the single machine scheduling problem in which the setup time depends on the sequence and the job family. The objective is to minimize the makespan and the total weighted tardiness. In order to solve the problem, two multi-objective algorithms are analyzed: one based on Multi-object...

Full description

Saved in:
Bibliographic Details
Main Authors: Ferreira Rego, Marcelo, Freitas Souza, Marcone Jamilson, Arroyo, Jose Elias Claudio
Format: Conference Proceeding
Language:English
Subjects:
Equations
Job shop scheduling
Mathematical model
Measurement
Multi-Objective Optimization
Multi-Objective Variable Neighborhood Search
Optimization
Pareto Iterated Local Search
Search problems
Single machine scheduling
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This work treats the single machine scheduling problem in which the setup time depends on the sequence and the job family. The objective is to minimize the makespan and the total weighted tardiness. In order to solve the problem, two multi-objective algorithms are analyzed: one based on Multi-objective Variable Neighborhood Search (MOVNS) and another on Pareto Iterated Local Search (PILS). Two literature algorithms based on MOVNS are adapted to solve the problem, resulting in the MOVNS Ottoni and MOVNS Arroyo variants. Also, a new perturbation procedure for the PILS is proposed, yielding the PILS1 variant. Computational experiments realized over test instances show that PILS1 is statistically better than all other algorithms in relation to the cardinality, average distance, maximum distance, difference of hypervolume and epsilon metrics.
ISSN:1522-4902
2691-0632
DOI:10.1109/SCCC.2012.24