Unrelated parallel machine scheduling with processing cost, machine eligibility and order splitting. (September 2022)

• Record Type: Journal Article
• Authors: Zheng, Feifeng; Jin, Kaiyuan; Xu, Yinfeng; Liu, Ming
• Is Part Of: Computers & industrial engineering. Volume 171(2022)
• Publication Date: 2022-09
• Subjects: 00-01 -- 99-00; Scheduling -- Manufacturing resource sharing -- Unrelated parallel machine -- Machine eligibility -- Order splitting -- Heuristic algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108483
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: Under the background of the emerging of shared manufacturing economics, this work addresses a new production order scheduling problem on unrelated parallel machines. Customer orders with release times are of various types depending on their specific product demands. Unrelated machines may be rented for processing orders via one cloud manufacturing service platform. It occurs a uniform processing cost once any machine is rented (via contract) for a given length time duration to process the orders. Each machine is generally able to process some but not all types of orders, i.e., machine eligibility is considered. Orders can be split into sub-orders and processed on their eligible machines simultaneously. For the objective of minimizing the weighted sum of total completion time of orders and total processing cost of machines being used, we establish a mixed integer linear programming model. We provide a lower bound of the considered problem by constraint relaxation, and present the pseudocode of an approach to obtain the lower bound. CPLEX is employed to generate optimal solutions for small-scale instances. For large-scale instances, two heuristic algorithms named Type-Based Greedy and Improved Differential Evolution are developed. The former algorithm selects a smallest set of machines to process the jobs and makes use of job splitting as much as possible, while the latter one is to acquire a best local optimal solution via finite times random global search in the feasible region. Computational experiments are carried out to demonstrate the efficiency and effectiveness of the proposed heuristics. Highlights: We combine the processing cost, machine eligibility and order splitting. A mathematical model is established. We conduct a theoretical lower bound for the problem. A Type-Based Greedy heuristic algorithm is developed. We propose an Improved Differential Evolution algorithm for the problem.