چکیده:
In some industries as foundries, it is not technically feasible to interrupt a processor between
jobs. This restriction gives rise to a scheduling problem called no-idle scheduling. This paper
deals with scheduling of no-idle open shops to minimize maximum completion time of jobs,
called makespan. The problem is first mathematically formulated by three different mixed
integer linear programming models. Since open shop scheduling problems are NP-hard, only
small instances can be solved to optimality using these models. Thus, to solve large instances,
two meta-heuristics based on simulated annealing and genetic algorithms are developed. A
complete numerical experiment is conducted and the developed models and algorithms are
compared. The results show that genetic algorithm outperforms simulated annealing.
خلاصه ماشینی:
"No-idle time Scheduling of Open shops: Modeling and Meta-heuristic Solution Methods b Bahman Naderia, Vahid Roshanaei aDepartment of Industrial Engineering, Kharazmi University, Tehran, Iran bDepartment of Industrial Engineering, University of Toronto, Toronto, Canada Abstract In some industries as foundries, it is not technically feasible to interrupt a processor between jobs.
This paper deals with scheduling of no-idle open shops to minimize maximum completion time of jobs, called makespan.
Since open shop scheduling problems are NP-hard, only small instances can be solved to optimality using these models.
Keywords: Scheduling, Open shop, No idle time, mixed integer linear programming, Simulated annealing, Genetic algorithm.
(2013) study the parallel open shop scheduling problem where each job has two independent non-preemptive operations.
(2014) study the multiprocessor open shop scheduling problem where there is a set of processing centers each of which has one or more parallel identical machines.
Deng and Gu (2012) present a hybrid discrete differential evolution algorithm for the no-idle permutation fowshop scheduling problem with makespan criterion.
Pan and Wang (2008) consider the no-idle permutation flow shop scheduling problems with the criterion to minimize makespan.
All the results supported that the models and metaheuristics effectively solve the no-idle open shop problem.
A hybrid discrete differential evolution algorithm for the no-idle permutation fow shop scheduling problem with makespan criterion.
A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem.
Some new results on simulated annealing applied to the job shop scheduling problem.
No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm."