A Matheuristic Algorithm for the Order Acceptance and Scheduling Problem
Ceyda Oğuz
Department of Industrial Engineering, Koç University

Abstract
Firms operating on a make-to-order basis may not satisfy the entire demand due to capacity limitations and tight delivery time requirements. This necessitates selecting only part of customer orders to maximize the total revenue, which gives rise to the order acceptance and scheduling (OAS) problems. In the OAS problem, we are given a single machine and a set of independent orders at the beginning of the planning period. For each order, there is an associated release time, processing time, due date, deadline, sequence dependent setup times, revenue and unit tardiness penalty cost. Each order should start after its release time and complete before its deadline; however, satisfying this requirement for all orders may not be possible due to the capacity limitations. An order satisfying this requirement (hence accepted for manufacturing) can be processed and completed until its deadline, but a tardiness penalty will be incurred for each time unit beyond its due date. This problem can be defined as a joint decision of which orders to accept and how to schedule the accepted orders.

Commercial solvers can solve the OAS problem only for moderate size instances, and there is a need for other approaches to solve realistic size problem instances, i.e., with large number of orders and with long planning horizon. In this study, we propose a two-phase iterative matheuristic algorithm (MATHEUR) for the OAS problem. In the first phase of MATHEUR, to exploit the good performance of the commercial solvers on moderate size problems, we decompose the planning horizon into smaller segments and solve a relaxed time-indexed model formulation for the OAS problem without setup times to assign orders to those time segments. In the second phase of MATHEUR, given the assignment information, we solve the OAS problem of each segment sequentially to generate a feasible solution to the original problem. This phase applies a tabu search algorithm to improve the obtained solution. This improved solution is then used to add cuts to the first phase. MATHEUR iteratively handles two phases until the stopping criterion is fulfilled. Preliminary runs show that the proposed algorithm can reach near optimal solutions for large size problems in minutes while commercial solvers cannot find competitive solutions within an hour.

(joint work with İstenç Tarhan)

Short Bio
Ceyda Oğuz is Professor of Industrial Engineering in College of Engineering at Koc University, Istanbul, Turkey. Before joining Koç University, she was a faculty member in the School of Business at The Hong Kong Polytechnic University, Hong Kong, from 1993 to 2004. She received her Ph.D. degree in Industrial Engineering from Bilkent University, Turkey, in 1993 and holds an M.S. degree (Bilkent University) and a B.S. degree (Middle East Technical University) both in Industrial Engineering. Prof. Oğuz conducts research in the areas of bioinformatics, logistics, and scheduling in manufacturing and computer systems. Her expertise includes algorithm design and system modeling as well as providing optimizing and/or approximate solutions to the complex systems by means of computational methods. Prof. Oğuz has participated in several research projects, which were funded by TUBITAK and jointly by the Hong Kong and the European governments, related to above fields. She has published in refereed journals such as Operations Research, Journal of Scheduling, Computers and Operations Research, and European Journal of Operational Research. Prof. Oğuz is an associate editor of Journal of Scheduling and also on the Editorial Board of Transportation Research Part E.

Venue
Friday, May 3, 2019 at 4.00 pm in IE03