Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job. (June 2020)

• Record Type: Journal Article
• Authors: Wang, Shijin; Wu, Ruochen; Chu, Feng; Yu, Jianbo
• Is Part Of: Computers & operations research. Volume 118(2020)
• Publication Date: 2020-06
• Subjects: Identical parallel machine scheduling -- Emergency job -- Maximum waiting time -- Makespan -- Total completion time; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.104918
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: This paper studies a variant Pm || F with high potential practical applications. A maximum waiting time is assured for an emergency job arrival at any time. The objectives of C max and ∑ Cj are considered separately. Two MIP models are formulated, which are improved with enhancement techniques. The 2-approximation ratio of classical heuristics are deduced for the case of C max . The NP-hardness is proven for the case of ∑ Cj . Formulation-based methods and effective heuristic methods are designed. Computational results demonstrate the efficacy of the proposed methods. Abstract: Currently, customer satisfaction is playing an increasingly vital role in both manufacturing and service industries. Assuring an acceptable waiting time to customers is considered as an effective approach to improve customer satisfaction. In this study, an identical parallel machine scheduling problem assuring the maximum waiting time for an emergency job which arrives at any time is investigated. A mixed integer programming model is formulated, based on which a variant formulation is generated. The formulations are further enhanced by various techniques, which forms two formulation-based methods. Two objectives, makespan and total completion time, are considered separately. Regarding the makespan, the worst-case approximation ratios of the classical heuristic rules are deduced. For the total completion time, efficient bounds are provided and the NP-hardness of the problem is proved. Heuristic methods based on the classical dispatch rules are developed, for both the cases. Extensive computational experiments are conducted, based on which the performances of the formulation-based methods and heuristics are compared, the relationship between the objective values and the assured maximum waiting time for an emergency job is explored, and a few observations and managerial insights are obtained.