Skip to Main content Skip to Navigation
Journal articles

Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job

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.
Document type :
Journal articles
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02493705
Contributor : Frédéric Davesne <>
Submitted on : Friday, February 28, 2020 - 9:30:27 AM
Last modification on : Monday, July 6, 2020 - 10:45:51 AM

Identifiers

Citation

Shijin Wang, Ruochen Wu, Feng Chu, Jianbo Yu. Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job. Computers and Operations Research, Elsevier, 2020, 118, pp.104918. ⟨10.1016/j.cor.2020.104918⟩. ⟨hal-02493705⟩

Share

Metrics

Record views

66