Open AccessParallel Machines Parts Ordering Problem with Time Window
Author(s) -
Bihui Cheng
Publication year - 2020
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/768/4/042014
Subject(s) - sorting , computer science , time complexity , window (computing) , constant (computer programming) , sorting algorithm , function (biology) , algorithm , parallel processing , parallel computing , mathematical optimization , mathematics , operating system , programming language , evolutionary biology , biology
in the classical sorting problem, the processing time of the job is usually a constant independent of the start time. However, in some sorting problems with strong practical background, the processing time of the job may have some relation with the starting time. It is divided into two cases, one is the processing time of the job is the increase function of the start time, the other is the processing time of the job is the decrease function of the start time. On the only one machine sorting problem with in time windows, this paper designs a 3/2-approximation algorithm for the parallel machiness parts sorting problem with in time windows, and its algorithm complexity is.