Hits:

Indexed by:Journal Papers

Date of Publication:2015-06-01

Journal:COMPUTERS & OPERATIONS RESEARCH

Included Journals:SCIE、EI、Scopus

Volume:58

Page Number:24-31

ISSN No.:0305-0548

Key Words:Scheduling; Flowshop; Learning effect; Heuristic algorithm; Branch-and-bound algorithm

Abstract:In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems. (C) 2014 Elsevier Ltd. All rights reserved.