Parallel-machine rescheduling with job unavailability and rejection

被引:60
作者
Wang, Dujuan [1 ]
Yin, Yunqiang [2 ]
Cheng, T. C. E. [3 ]
机构
[1] Sichuan Univ, Business Sch, Chengdu 610064, Sichuan, Peoples R China
[2] Univ Elect Sci & Technol China, Sch Management & Econ, Chengdu 611731, Sichuan, Peoples R China
[3] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Kowloon, Hong Kong, Peoples R China
来源
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE | 2018年 / 81卷
基金
中国国家自然科学基金; 中国博士后科学基金;
关键词
Scheduling; Branch-and-price; Dynamic programming; Differential evolution; TOTAL COMPLETION-TIME; SINGLE-MACHINE; SCHEDULING PROBLEM; ORDER ACCEPTANCE; DISRUPTION; MULTIPLE; POLICIES;
D O I
10.1016/j.omega.2018.04.008
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We study the scheduling problem where a set of jobs has already been scheduled for processing on identical parallel machines to minimize the total completion time under the assumption that all the jobs are available at time zero. However, before processing begins, some jobs are delayed and become unavailable at time zero, so all the jobs need to be rescheduled with a view to not causing excessive schedule disruption with respect to the original schedule. To reduce the negative impact of job unavailability and achieve an acceptable service level, one option in rescheduling the jobs is to reject a subset of the jobs at a cost (the rejection cost). Three criteria are involved: the total completion time of the accepted jobs in the adjusted schedule, the degree of disruption measured by the maximum completion time disruption to any accepted job between the original and adjusted schedules, and the total rejection cost. The overall objective is to minimize the former criterion, while keeping the objective values of the latter two criteria to no greater than the given limits. We present two exact methods to solve the problem: (i) A dynamic programming based approach, establishing that the problem is NA-hard in the ordinary sense when the number of machines is fixed. (ii) An enhanced branch-and-price method that includes several features such as execution of the differential evolution algorithm for finding good initial feasible solutions and solving the pricing sub-problem, inclusion of reduced cost fixing during the inner iterations of the algorithm, and use of a heuristic procedure for constructing a good integer feasible solution. We perform extensive computational experiments to assess the efficiency of the proposed algorithms. The computational results demonstrate that the incorporated enhancements greatly improve the performance of the algorithm. (C) 2018 Elsevier Ltd. All rights reserved.
引用
收藏
页码:246 / 260
页数:15
相关论文
共 50 条
  • [21] Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
    Zheng, Hongye
    Gao, Suogang
    Liu, Wen
    Wu, Weili
    Du, Ding-Zhu
    Hou, Bo
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (01) : 343 - 353
  • [22] Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
    Hongye Zheng
    Suogang Gao
    Wen Liu
    Weili Wu
    Ding-Zhu Du
    Bo Hou
    Journal of Combinatorial Optimization, 2022, 44 : 343 - 353
  • [23] Parallel-machine scheduling with deteriorating jobs, rejection and a fixed non-availability interval
    Zhang, Minjiao
    Luo, Chengxin
    APPLIED MATHEMATICS AND COMPUTATION, 2013, 224 : 405 - 411
  • [24] Rescheduling of unrelated parallel machines with job-dependent setup times under forecasted machine breakdown
    Kim, Young-In
    Kim, Hyun-Jung
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2021, 59 (17) : 5236 - 5258
  • [25] A fast heuristic algorithm for solving parallel-machine job-shop scheduling problems
    Gholami, Omid
    Sotskov, Yuri N.
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2014, 70 (1-4) : 531 - 546
  • [26] A fast heuristic algorithm for solving parallel-machine job-shop scheduling problems
    Omid Gholami
    Yuri N. Sotskov
    The International Journal of Advanced Manufacturing Technology, 2014, 70 : 531 - 546
  • [27] Unrelated parallel-machine scheduling with deteriorating maintenance activities
    Cheng, T. C. E.
    Hsu, Chou-Jung
    Yang, Dar-Li
    COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 60 (04) : 602 - 605
  • [28] Parallel-machine scheduling with time dependent processing times
    Kuo, Wen-Hung
    Yang, Dar-Li
    THEORETICAL COMPUTER SCIENCE, 2008, 393 (1-3) : 204 - 210
  • [29] Parallel-machine scheduling with machine-dependent maintenance periodic recycles
    Li, Guo
    Liu, Mengqi
    Sethi, Suresh P.
    Xu, Dehua
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2017, 186 : 1 - 7
  • [30] A parallel-machine scheduling problem with two competing agents
    Lee, Wen-Chiung
    Chung, Yu-Hsiang
    Wang, Jen-Ya
    ENGINEERING OPTIMIZATION, 2017, 49 (06) : 962 - 975