A three-agent scheduling problem for minimizing the makespan on a single machine

•A three-agent scheduling problem regarding minimizing the makespan.•A branch-and-bound algorithm to search for the optimal solution.•An enhanced genetic algorithm with a dedicated local search. Scheduling with multiple competing agents has drawn considerable attention lately. However, most traditio...

Full description

Saved in:
Bibliographic Details
Published in:Computers & industrial engineering 2017-04, Vol.106, p.147-160
Main Authors: Lee, Wen-Chiung, Wang, Jen-Ya
Format: Article
Language:English
Subjects:
Branch-and-bound algorithm
Job scheduling
Maintenance activity
Makespan
Multi-agent
Tardiness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•A three-agent scheduling problem regarding minimizing the makespan.•A branch-and-bound algorithm to search for the optimal solution.•An enhanced genetic algorithm with a dedicated local search. Scheduling with multiple competing agents has drawn considerable attention lately. However, most traditional studies have focused on two-agent scheduling only. In this study, we consider a single-machine three-agent scheduling problem. The objective is to minimize the makespan of jobs from agent 1 given that the maximum tardiness of jobs from agent 2 cannot exceed a limit and that a maintenance activity from agent 3 must be completed within a specified maintenance window. Several dominance rules and a lower bound based on job preemption are proposed. A branch-and-bound algorithm and a genetic algorithm are proposed to obtain optimal and approximate solutions, respectively. Experimental results show that the dominance rules and lower bound can eliminate the unnecessary nodes and improve the execution time greatly.
ISSN:0360-8352
1879-0550
DOI:10.1016/j.cie.2017.02.001