یک رویکرد مدل سازی بهینه برای بهینه سازی آنلاین با جستجوگر  A general modeling approach to online optimization with lookahead

1. Introduction Although there is an agreement on the importance of coping with unexpected events in today’s systems for production and logistics [26,51], recent implementations of planning and scheduling systems still suffer from their deficiency in dealing with uncertainty over time. In a rolling horizon, plans are determined on the basis of forecasts by offline optimization methods [51]. However, since only decisions of the next period are implemented before the problem gets resolved with updated data, this approach exhibits large redundancies. On the other hand, possibilities for collection of data about near-future events are steadily increasing due to technological developments [26] such as radio frequency identification (RFID), global positioning systems (GPS) or geographical information systems (GIS). Since planning systems in these environments are subject to permanent information inflow, they are said to be online. Optimization problems in this context are called online optimization problems [24]. These problems are characterized by the fact that decisions are required to be made repeatedly before all data is available. In contrast to other methodologies for optimization under uncertainty, there are no forecasts or probabilities of future events assumed in online optimization. However, as a result of technological opportunities given above, we can now cope with uncertainty differently. Through the installation of lookahead devices, it is possible to acquire data about future events at an earlier point in time. Hence, uncertainty is tackled forcefully because parts of the previously uncertain future can now be fixed to certainty through the utilization of lookahead. Thus, the decision making process consists of repetitive decisions where the input to each decision only consists of the small, but certain part of the future known at that time. Though, as can be seen from the different information gathering devices mentioned above, it may be reasonable to be more precise with respect to the actual degree of “onlineness” in a specific problem setting. The need for a concise notion of lookahead is also reflected by the manifold perceptions of lookahead depending on the application [2–4,14,17,29,37,45,52,56]. For this reason, this paper coins the notion of online optimization with lookahead on a formal basis. The task of solving online optimization problems is a recurring pattern in industrial applications (Fig. 1): each time the functional logic of a dynamic system requires a decision, an online algorithm is called to deliver it, i.e., partial answers based on currently available data have to be given such that the overall solution will be as good as possible. Solution methodologies for the different optimization paradigms strongly differ from each other. Consider the input sequence σ ¼ ðσ1; σ2; …Þ. In offline optimization, σ is known in advance and a plan for how to process its elements can be computed directly. In the sequential model of online optimization [30], only one input element is known at a time and input elements must be processed in release order, i.e., input element σi is processed based upon knowledge of σ1; …; σi and previous decisions on σ1; …; σi1. In the time-stamp model [30], each input element is assigned an arrival date such that input elements may accumulate naturally and automatically form some lookahead set of unprocessed input elements. In online optimization with request lookahead [2,52], more than one unprocessed input element may be known at a time and also an explicit formulation of processing restrictions is required. One could insist on sequential processing (σi must be processed before σiþ1) or allow for a processing in arbitrary order (σiþ1 can be processed before σi). There are a plenty of variations of how lookahead is understood and what it means for the processing of single input elements. For this reason, this paper will provide the tools for classifying the main features of a specific online optimization problem with lookahead.