Makespan Minimization for Parallel Machines Environment with Machine Dependent Processing Time by Using PBIL Combined with Local Search

Pensiri Sompong, Sungkom Srisomporn

Abstract


Population-based incremental learning algorithm (PBIL) is proposed to solve parallel machines scheduling problem with machine dependent processing time. The initial population of proposed algorithm is created based on probability vector resulting from the solution obtained from applying shortest processing time (SPT) dispatching rule for parallel machines to represent the jobs assigned on the machines. Local search is performed during the process to move a job to an appropriate machine that makespan is minimized. The performance of the algorithm is illustrated by numerical examples. The solutions obtained from PBIL are compared to the solution from SPT. The results show that the assignment of jobs by using PBIL combined with local search can reduce makespan and it is suitable for solving parallel machines scheduling problem with machine dependent processing time.


Full Text: PDF

Refbacks

  • There are currently no refbacks.


The Thai Journal of Mathematics organized and supported by The Mathematical Association of Thailand and Thailand Research Council and the Center for Promotion of Mathematical Research of Thailand (CEPMART).

Copyright 2020 by the Mathematical Association of Thailand.

All rights reserve. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission of the Mathematical Association of Thailand.

|ISSN 1686-0209|