Sum-of-processing-times-based two-agent single-machine scheduling with aging effects and tardiness (Q1666548)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sum-of-processing-times-based two-agent single-machine scheduling with aging effects and tardiness |
scientific article |
Statements
Sum-of-processing-times-based two-agent single-machine scheduling with aging effects and tardiness (English)
0 references
27 August 2018
0 references
Summary: We consider a two-agent single-machine scheduling problem that minimizes the total weighted tardiness of one agent under the restriction that the second agent is prohibited from having tardy jobs. The actual processing times of all jobs are affected by a sum-of-processing-times-based aging effect. After showing the NP-hardness of the problem, we design a branch-and-bound (B\&B) algorithm to find an optimal solution by developing dominance properties and a lower bound for the total weighted tardiness to increase search efficiency. Because B\&B takes a long time to find an optimal solution, we propose a genetic algorithm as an efficient, near optimal solution approach. Four methods for generating initial populations are considered, and edge recombination crossover is adopted as a genetic operator. Through numerical experiments, we verify the outstanding performance of the proposed genetic algorithm.
0 references
0 references
0 references
0 references
0 references
0 references