6533b86cfe1ef96bd12c81f3
RESEARCH PRODUCT
An approximate/exact objective based search technique for solving general scheduling problems
Andrzej KozikRadosław Rudeksubject
Rate-monotonic schedulingMathematical optimization021103 operations researchSingle-machine schedulingJob shop schedulingComputer science0211 other engineering and technologiesaging effectmetaheuristic02 engineering and technologyDynamic priority schedulingsetup timeFair-share schedulingScheduling (computing)Metaheuristic algorithmsTwo-level scheduling0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingschedulingmaintenance activitySoftwareprecedence constraintsdescription
Abstract In this paper, we analyze single machine scheduling problems under the following minimization objectives: the maximum completion time (makespan), the total completion time and the maximum lateness, including fundamental practical aspects, which often occur in industrial or manufacturing reality: release dates, due dates, setup times, precedence constraints, deterioration (aging) of machines, as well as maintenance activities. To solve the problems, we propose an efficient representation of a solution and a fast neighborhood search technique, which calculates an approximation of criterion values in a constant time per solution in a neighborhood. On this basis, a novel approximate/exact search technique, using exact as well as approximate criterion values during search process, is introduced and used to develop efficient metaheuristic algorithms dedicated to the considered problems. Their efficiency is verified during computational experiments.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2018-01-01 | Applied Soft Computing |