Order acceptance and scheduling on two identical parallel machines

Xiuli Wang, Guodong Huang, Xiuwu Hu, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

We study the order acceptance and scheduling problem on two identical parallel machines. At the beginning of the planning horizon, a firm receives a set of customer orders, each of which has a revenue value, processing time, due date, and tardiness weight. The firm needs to select orders to accept and schedule the accepted orders on two identical parallel machines so as to maximize the total profit. The problem is intractable, so we develop two heuristics and an exact algorithm based on some optimal properties and the Lagrangian relaxation technique. We evaluate the performance of the proposed solution methods via computational experiments. The computational results show that the heuristics are efficient and effective in approximately solving large-sized instances of the problem, while the exact algorithm can only solve small-sized instances.
Original languageEnglish
Pages (from-to)1755-1767
Number of pages13
JournalJournal of the Operational Research Society
Volume66
Issue number10
DOIs
Publication statusPublished - 1 Jan 2015

Keywords

  • order acceptance
  • parallel machines
  • profit
  • scheduling

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Cite this