Indexed by:
Abstract:
The controllable processing times (CPTs) have many practical applications, enabling the length of the job processing to vary within an interval flexibly with additional costs. In this paper, we study an unrelated parallel machine scheduling problem with machine-and sequence-dependent setup times and a special case of CPTs without extra costs. The objective is to maximize the difference between the sum of realized state of processing of all jobs and makespan. To solve the problem, a mixed integer programming (MIP) model is formulated first and then a logic-based Benders decomposition (LBBD) method is developed, in which the master problem is for job assignments and the subproblem is furthered decomposed into a sequencing problem for minimum total setup times on each machine and a processing time determination problem. Several LBBD-based heuristics are also employed by imposing different optimality gaps for the master problem. The performance of the MIP formulation, the exact LBBD method and the LBBD-based heuristics is compared through extensive computational experiments. The results demonstrate that the exact LBBD method with the preprocessing procedure which generates initial feasible solutions and cuts is effective and the proposed LBBD-based heuristics reduce the computation time significantly at the expense of slightly solution quality reduction.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
COMPUTERS & OPERATIONS RESEARCH
ISSN: 0305-0548
Year: 2022
Volume: 148
4 . 6
JCR@2022
4 . 1 0 0
JCR@2023
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:61
JCR Journal Grade:2
CAS Journal Grade:2
Cited Count:
SCOPUS Cited Count: 5
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: