E-resources
Peer reviewed
Open access
-
Li, Xin; Ventura, José A.; Bunn, Kevin A.
Journal of scheduling, 02/2021, Volume: 24, Issue: 1Journal Article
This paper considers a joint order acceptance and scheduling problem under a general scenario. A manufacturer receives multiple orders with a given revenue, processing time, release date, due date, deadline, and earliness and tardiness penalties. The manufacturer can be seen as a single-machine system. Due to limited capacity, the manufacturer cannot process every order and needs to determine the optimal set of accepted orders and corresponding production schedule such that the total profit is maximized. The manufacturer can extend its capacity with overtime by paying an additional cost. A time-indexed formulation is presented to model the problem. Two exact algorithms are proposed. The first algorithm, denoted by DPIA-GR, is a dynamic programming (DP)-based algorithm that starts by solving a relaxed version of the original model and successively recovers the relaxed constraint until an optimal solution to the original problem is achieved. The second algorithm, denoted by DPIA-LRGR, improves DPIA-GR by incorporating Lagrangian relaxation (LR). The subgradient method is employed to find the optimal Lagrangian multipliers. The relaxed model in DPIA-GR and the LR model in DPIA-LRGR can be represented using a weighted di-graph. Both algorithms are equivalent to finding the longest path in the graph and applying a graph reduction strategy to prevent unnecessary computational time and memory usage. A genetic algorithm (GA) is also proposed to solve large-scale versions of the problem. Numerical experiments show that both DPIA-GR and DPIA-LRGR solve the problem efficiently and outperform CPLEX and GA, but DPIA-LRGR offers better performance.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.