Parallel machine scheduling with step deteriorating jobs and setup times by a hybrid discrete cuckoo search algorithm
This article considers the parallel machine scheduling problem with step-deteriorating jobs and sequence-dependent setup times. The objective is to minimize the total tardiness by determining the allocation and sequence of jobs on identical parallel machines. In this problem, the processing time of each job is a step function dependent upon its starting time. An individual extended time is penalized when the starting time of a job is later than a specific deterioration date. The possibility of deterioration of a job makes the parallel machine scheduling problem more challenging than ordinary ones. A mixed integer programming model for the optimal solution is derived. Due to its NP-hard nature, a hybrid discrete cuckoo search algorithm is proposed to solve this problem. In order to generate a good initial swarm, a modified heuristic named the MBHG is incorporated into the initialization of population. Several discrete operators are proposed in the random walk of L\'{e}vy Flights and the crossover search. Moreover, a local search procedure based on variable neighborhood descent is integrated into the algorithm as a hybrid strategy in order to improve the quality of elite solutions. Computational experiments are executed on two sets of randomly generated test instances. The results show that the proposed hybrid algorithm can yield better solutions in comparison with the commercial solver CPLEX with one hour time limit, discrete cuckoo search algorithm and the existing variable neighborhood search algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
SchedulingSimilar Papers 제목 키워드 기반
Multi-Job Intelligent Scheduling with Cross-Device Federated Learning
Recent years have witnessed a large amount of decentralized data in various (edge) devices of end-users, while the decentralized data aggregation remains complicated for machine learning jobs because of regulations and l…
Bayesian OptimizationFairnessFederated LearningSchedulingExact and heuristic methods for the discrete parallel machine scheduling location problem
The discrete parallel machine makespan scheduling location (ScheLoc) problem is an integrated combinatorial optimization problem that combines facility location and job scheduling. The problem consists in choosing the lo…
ARCCombinatorial OptimizationSchedulingDeep Learning for Unrelated-Machines Scheduling: Handling Variable Dimensions
Deep learning has been effectively applied to many discrete optimization problems. However, learning-based scheduling on unrelated parallel machines remains particularly difficult to design. Not only do the numbers of jo…
Efficient Device Scheduling with Multi-Job Federated Learning
Recent years have witnessed a large amount of decentralized data in multiple (edge) devices of end-users, while the aggregation of the decentralized data remains difficult for machine learning jobs due to laws or regulat…
Bayesian OptimizationFairnessFederated LearningSchedulingA mathematical model for simultaneous personnel shift planning and unrelated parallel machine scheduling
This paper addresses a production scheduling problem derived from an industrial use case, focusing on unrelated parallel machine scheduling with the personnel availability constraint. The proposed model optimizes the pro…
Decision MakingScheduling