3.1. OR in banking

In this paper, we describe a deterministic multiperiod capacity expansion model in which a single facility serves the demand for many products. Potential applications for the model can be found in the capacity expansion planning of communication systems as well as in the production planning of heavy process industries. The model assumes that each capacity unit simultaneously serves a prespecified (though not necessarily integer) number of demand units of each product. Costs considered include capacity expansion costs, idle capacity holding costs, and capacity shortage costs. All cost functions are assumed to be nondecreasing and concave. Given the demand for each product over the planning horizon, the objective is to find the capacity expansion policy that minimizes the total cost incurred. We develop a dynamic programming algorithm that finds optimal policies. The required computational effort is a polynomial function of the number of products and the number of time periods. When the number of products equals one, the algorithm reduces to the well-known algorithm for the classical dynamic lot size problem.     

Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties

This paper is concerned with the problem of scheduling n jobs with a common due date on a single machine so as to minimize the total cost arising from earliness and tardiness. A general model is examined, in which earliness penalty and tardiness penalty are, respectively, arbitrary non-decreasing functions. Moreover, the model includes two important features that commonly appear in practical problems, namely, 1) earliness and tardiness are penalized with different weights which are job-dependent, and 2) the earliness (or tardiness) penalty consists of two parts, one is a variable cost dependent on the length of earliness (or tardiness), while the other is a fixed cost incurred when a job is early (or tardy). This model provides a general and flexible performance measure for earliness/tardiness scheduling, which has not been addressed before. We establish a number of results on the characterizations of optimal and sub-optimal solutions, and propose two algorithms based on these results. The first algorithm can find, under an agreeable weight condition, an optimum in time O(n² P_n), and the second algorithm can generate a sub-optimum in time O(nP_n), where P_n is the sum of the processing times. Further, we derive an upper bound on the relative error of the sub-optimal solution and show that, under certain conditions, the error tends to zero as n increases. Computational results are also reported to demonstrate the effectiveness of the algorithms proposed.     

Scheduling with batch setup times and earliness-tardiness penalties

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.     

Optimal timing of a sequence of tasks with general completion costs

Scheduling a sequence of tasks––in the acceptation of finding the execution times––is not a trivial problem when the optimization criterion is irregular as for instance in earliness–tardiness problems. This paper presents an efficient dynamic programming algorithm to solve the problem with general cost functions depending on the end time of the tasks, idle time costs and variable durations also depending on the execution time of the tasks. The algorithm is also valid when the precedence graph is a tree and it can be adapted to determine the possible execution windows for each task not exceeding a maximum fixed cost.     

具有老化效应的单机共同工期安排和工件可拒绝排序问题

研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。     

Reinforcement learning for joint pricing,lead-time and scheduling decisions in make-to-order systems

The paper investigates a problem faced by a make-to-order (MTO) firm that has the ability to reject or accept orders, and set prices and lead-times to influence demands. Inventory holding costs for early completed orders, tardiness costs for late delivery orders, order rejection costs, manufacturing variable costs, and fixed costs are considered. In order to maximize the expected profits in an infinite planning horizon with stochastic demands, the firm needs to make decisions from the following aspects: which orders to accept or reject, the trade-off between price and lead-time, and the potential for increased demand against capacity constraints. We model the problem as a Semi-Markov Decision Problem (SMDP) and develop a reinforcement learning (RL) based Q-learning algorithm (QLA) for the problem. In addition, we build a discrete-event simulation model to validate the performance of the QLA, and compare the experimental results with two benchmark policies, the First-Come-First-Serve (FCFS) policy and a threshold heuristic policy. It is shown that the QLA outperforms the existing policies.     

Lower bounds for the earliness–tardiness scheduling problem on parallel machines with distinct due dates

This paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed formulation of the problem is investigated in order to derive efficient lower bounds throught column generation or Lagrangean relaxation. A simple local search algorithm is also presented in order to derive an upper bound. Computational experiments compare these bounds for both the one machine and parallel machine problems and show that the gap between upper and lower bounds is about 1.5%.     

Order acceptance and scheduling with earliness and tardiness penalties

This paper addresses a production scheduling problem in a single-machine environment, where a job can be either early, on time, late, or rejected. In order acceptance and scheduling contexts, it is assumed that the production capacity of a company is overloaded. The problem is therefore to decide which orders to accept and how to sequence their production. In contrast with the existing literature, the considered problem jointly takes into account the following features: earliness and tardiness penalties (which can be linear or quadratic), sequence-dependent setup times and costs, rejection penalties, and the possibility of having idle times. The practical relevance of this new NP-hard problem is discussed and various solution methods are proposed, ranging from a basic greedy algorithm to refined metaheuristics (e.g., tabu search, the adaptive memory algorithm, population-based approaches loosely inspired on ant algorithms). The methods are compared for instances with various structures containing up to 200 jobs. For small linear instances, the metaheuristics are favorably compared with an exact formulation using CPLEX 12.2. Managerial insights and recommendations are finally given.     

A noniterative multiproduct multiperiod production planning method

Production planning for multiple products on a single production facility over a time horizon requires minimizing the sum of production costs (regular time, overtime and subcontracting) and inventory carrying costs for meeting the known demands of the products. It is shown that the problem can be formulated and solved by a simple and noniterative method of ‘column minima’ even for multiple product situations.     

优化交货期窗口的两阶段供应链排序问题

研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.     

Minimizing earliness and tardiness penalties in a single-machine problem with a common due date

Scheduling problems involving both earliness and tardiness costs have received significant attention in recent years. This type of problem became important with the advent of the just-in-time (JIT) concept, where early or tardy deliveries are highly discouraged. In this paper we examine the single-machine scheduling problem with a common due date. Performance is measured by the minimization of the sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, we propose a tabu search-based heuristic and a genetic algorithm which exploit specific properties of the optimal solution. Hybrid strategies are also analyzed to improve the performance of these methods. The proposed approaches are examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs.     

Parallel machine scheduling with a common due window

In this paper, we consider a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized. Specifically, we consider the problem with a set of independent jobs to be processed on several identical parallel machines. All the jobs have a given common due window. If a job is completed within the due window, then there is no penalty. Otherwise, there is either a job-dependent earliness penalty or a job-dependent tardiness penalty depending on whether the job is completed before or after the due window. The objective is to find an optimal schedule with minimum total earliness–tardiness penalty. The problem is known to be NP-hard. We propose a branch and bound algorithm for finding an optimal schedule of the problem. The algorithm is based on the column generation approach in which the problem is first formulated as a set partitioning type formulation and then in each branch and bound iteration the linear relaxation of this formulation is solved by the standard column generation procedure. Our computational experiments show that this algorithm is capable of solving problems with up to 40 jobs and any number of machines within a reasonable computational time.     

An evaluation of heuristics for scheduling a non-delay permutation flow shop with family setups to minimize total earliness and tardiness

This paper presents several procedures for developing non-delay schedules for a permutation flow shop with family setups when the objective is to minimize total earliness and tardiness. These procedures consist of heuristics that were found to be effective for minimizing total tardiness in flow shops without family setups, modified to consider family setups and the total earliness and tardiness objective. These procedures are tested on several problem sets with varying conditions. The results show that variable greedy algorithms are effective when solving small problems, but using a genetic algorithm that includes a neighbourhood defined by the sequence of batches of jobs belonging to the same set-up family is effective when solving medium- or large-sized problems. The results also show that if setup times can be reduced a significant reduction in total earliness and tardiness could result.     

An exact algorithm for the bi-objective timing problem

The timing problem in the bi-objective just-in-time single-machine job-shop scheduling problem (JiT-JSP) is the task to schedule N jobs whose order is fixed, with each job incurring a linear earliness penalty for finishing ahead of its due date and a linear tardiness penalty for finishing after its due date. The goal is to minimize the earliness and tardiness simultaneously. We propose an exact greedy algorithm that finds the entire Pareto front in \(O(N^2)\) time. This algorithm is asymptotically optimal.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

基于仿真优化的炼钢生产批调度求解方法

论文针对钢铁企业炼钢工序具有高温、高能耗、复杂工况的实际特征,从中提炼出生产批调度问题,其工件根据其实际工艺属性可分为多个簇,基于给定的工件簇,决策工件的分批和调度情况,综合考虑工件之间的切换费用,以及工件提前、拖期所导致的惩罚,使得总的生产成本期望最小化,从而降低生产成本;针对该问题,考虑工件的处理时间、工件的加工属性具有不确定性,基于仿真优化思想,建立数学模型,并基于大数定理,对模型目标函数进行近似;提出基于样本近似方法的求解框架,通过随机抽样的方法获得不同规模的样本,针对不同规模的样本,提出Filter & Fan算法对问题进行求解;最后,通过基于实际数据的计算实验验证所提算法的有效性。     

The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times

We study the earliness-tardiness scheduling problem on a single machine with due date assignment and controllable processing times. We analyze the problem with three different due date assignment methods and two different processing time functions. For each combination of these, we provide a polynomial-time algorithm to find the optimal job sequence, due date values and resource allocation minimizing an objective function which includes earliness, tardiness, due date assignment, makespan and total resource consumption costs.     

Minimizing weighted earliness–tardiness and due-date cost with unit processing-time jobs

The classical single-machine scheduling and due-date assignment problem of Panwalker et al. [Panwalker, S.S., Smith, M.L., Seidmann, A., 1982. Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30(2) (1982) 391–399] is the following: All n jobs share a common due-date, which is to be determined. Jobs completed prior to or after the due-date are penalized according to a cost function which is linear and job-independent. The objective is to minimize the total earliness–tardiness and due-date cost. We study a generalized version of this problem in which: (i) the earliness and tardiness costs are allowed to be job dependent and asymmetric and (ii) jobs are processed on parallel identical machines. We focus on the case of unit processing-time jobs. The problem is shown to be solved in polynomial (O(n⁴)) time. Then we study the special case with no due-date cost (a classical problem known in the literature as TWET). We introduce an O(n³) solution for this case. Finally, we study the minmax version of the problem, (i.e., the objective is to minimize the largest cost incurred by any of the jobs), which is shown to be solved in polynomial time as well.     

Single machine scheduling problem with multiple due windows assignment in a group technology

We consider group scheduling problem on a single machine with multiple due windows assignment. Jobs are divided into groups in advance according to their processing similarities, and all jobs of the same group are required to be processed contiguously on the machine in order to achieve production efficiency and save time/money resource. A sequence-independent setup time precedes the processing of each group. The goal is to determine the optimal sequence for both groups and jobs, together with an optimal combination of the due windows assignment strategy so as to minimize the total of earliness, tardiness and due windows related costs. We give an \(O(n\log n)\) time algorithm for the problem.     

Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions

The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the capacitated lot sizing problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.