|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Customer Order Scheduling to Minimize the Number of Late Jobsстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Kononov A., Lin B.M.-T
- Журнал: European Journal of Operational Research
- Том: 183
- Номер: 2
- Год издания: 2007
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 944
- Последняя страница: 948
- DOI: 10.1016/j.ejor.2006.10.021
- Аннотация: In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for thetwo-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date.
- Добавил в систему: Кононов Александр Вениаминович