Details

Autor(en) / Beteiligte

• Meng, Tao
• Pan, Quan-Ke
• Wang, Ling

Titel

A distributed permutation flowshop scheduling problem with the customer order constraint

Ist Teil von

• Knowledge-based systems, 2019-11, Vol.184, p.104894, Article 104894

Ort / Verlag

Amsterdam: Elsevier B.V

Erscheinungsjahr

2019

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• In the classic distributed permutation flowshop scheduling problem (DPFSP), jobs are viewed as individual entities and processed independently. In many practical cases, however, a number of jobs actually come from the same customer order. Under this circumstance, it may be sensible to process jobs from the same customer order in a single factory to reduce transportation costs, paperwork and management burden. This study introduces the customer order constraint into the DPFSP. In our problem, a set of customer orders need to be manufactured in a number of factories and each order composed of some defined jobs should be processed in the same factory. The objective is to minimize the maximum completion time or makespan among factories. At first, we build a mathematical model to formulate this new problem. Then, given the NP-hardness of this problem, we present three heuristics exploring three rules for generating the seed job sequence as well as two rules for assigning orders to factories. Besides, we develop three meta-heuristics, namely, a variable neighborhood descent (ORVND), an artificial bee colony (ORABC) and an iterated greedy (ORIG). Effective mechanisms are suggested to improve the performance, including an order-insertion based neighborhood search and a greedy reinsertion strategy for ORVND, a two-level search scheme and a multi-neighbor scheme for ORABC, and the improved destruction, reconstruction and local search operations for ORIG. Finally, extensive experiments based on famous benchmarks are performed and numerical comparisons validate the high effectiveness of presented algorithms for the considered problem. •We introduce the customer order constraint into the DPFSP.•We build an MILP model to formulate this new problem.•We propose three heuristics inspired by the NEH2 method.•We develop three meta-heuristics with problem-specific strategies.•Experimental results demonstrate the effectiveness of presented algorithms.