A meta-heuristic for minimizing total weighted flow time on parallel batch machines. (November 2018)

• Record Type: Journal Article
• Authors: Jia, Zhao-hong; Zhang, Han; Long, Wen-tao; Leung, Joseph Y-T.; Li, Kai; Li, Wei
• Is Part Of: Computers & industrial engineering. Volume 125(2018)
• Page Start: 298
• Page End: 308
• Publication Date: 2018-11
• Subjects: Parallel scheduling -- Patch processing machines -- Non-identical job sizes -- Total weighted completion time -- Ant colony optimization algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.08.009
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We consider minimizing the total weighted completion time of scheduling on parallel batch machines. We present a MIP formulation of the problem and a lower bound. An ACO-based meta-heuristic is proposed to solve the problem. We compare our algorithm with a deterministic algorithm and one state-of-the-art algorithm. Computational results show that our algorithm outperforms the other algorithms. Abstract: To address the problem of minimizing the total weighted completion time on parallel batch processing machines with identical machine capacities, non-identical job sizes and unequal weights, an effective meta-heuristic based on ant colony optimization is proposed. After presenting a mathematic model of the problem, we provide an algorithm to calculate the lower bound. Then, a meta-heuristic is proposed to solve the problem. The heuristic information is defined with consideration of job weights and job sizes. Meanwhile, a candidate set for constructing the solution is used to narrow the search space. Additionally, to improve the solution quality, a local optimization strategy is incorporated. Simulation results show that the proposed algorithm is able to obtain a high-quality solution within a reasonable time, and outperforms the compared algorithms.