A Joint Order Acceptance and Scheduling Problem with Earliness and Tardiness Penalties Considering Overtime

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.

This is a post-peer-review, pre-copyedit version of an article published in 'Journal of Scheduling'. The final authenticated version is available online at: https://doi.org/10.1007/s10951-020-00672-5. The following terms of use apply: https://www.springer.com/gp/open-access/publication-policies/aam-terms-of-use.


  • OASTEO+v6+sub-1.docx

    size: 1.57 MB | mime_type: application/vnd.openxmlformats-officedocument.wordprocessingml.document | date: 2021-09-09


Work Title A Joint Order Acceptance and Scheduling Problem with Earliness and Tardiness Penalties Considering Overtime
Open Access
  1. Xin Li
  2. José A. Ventura
  3. Kevin A. Bunn
License In Copyright (Rights Reserved)
Work Type Article
  1. Springer Science and Business Media LLC
Publication Date October 22, 2020
Publisher Identifier (DOI)
  1. 10.1007/s10951-020-00672-5
  1. Journal of Scheduling
Deposited September 09, 2021




This resource is currently not in any collection.

Work History

Version 1

  • Created
  • Added OASTEO+v6+sub-1.docx
  • Added Creator Xin Li
  • Added Creator José A. Ventura
  • Added Creator Kevin A. Bunn
  • Published
  • Updated
  • Updated