Back to Search Start Over

An integrated approach for allocation and scheduling-location problems on graphs

Authors :
Nguyen, Kien Trung
Le, Huy Minh
Source :
Computational and Applied Mathematics; April 2024, Vol. 43 Issue: 3
Publication Year :
2024

Abstract

This article uses an integrated approach to solve real-world problems in three areas, namely single machine scheduling, 1-center location on networks and nonrenewable allocation problems. Jobs are stored at vertices and a single machine will be placed in the network. Each job receives an allocation that comes with a specific cost from an expected limited budget. Processing times of jobs are considered continuous functions of the allocation variables multiplied by costs, while release dates are defined as distances from job locations to the machine. We call this problem the scheduling-location problem with job allocation. The goal is to find a location on networks and an allocation to minimize a scheduling objective, makespan. We first consider the problem at a fixed location and propose a combinatorial algorithm that repeatedly solves continuous knapsack problems and runs in quadratic time. Concerning the original problem, we explore some properties of the objective function and develop a polynomial time algorithm to solve it.

Details

Language :
English
ISSN :
22383603 and 18070302
Volume :
43
Issue :
3
Database :
Supplemental Index
Journal :
Computational and Applied Mathematics
Publication Type :
Periodical
Accession number :
ejs65940620
Full Text :
https://doi.org/10.1007/s40314-024-02650-5