Online scheduling of ordered flow shops

We consider online as well as offline scheduling of ordered flow shops with the makespan as objective. In an online flow shop scheduling problem, jobs are revealed to a decisionmaker one by one going down a list. When a job is revealed to the decision maker, its operations have to be scheduled irrevocably without having any information regarding jobs that will be revealed afterwards. We consider for the online setting the so-called Greedy Algorithm which generates permutation schedules in which the jobs on the machines are at all times processed without any unnecessary delays. We focus on ordered flow shops, in particular proportionate flow shops with different speeds and proportionate flow shops with different setup times. We analyze the competitive ratio of the Greedy Algorithm for such flow shops in the online setting. For several cases, we derive lower bounds on the competitive ratios.     

Designing coalition-based fair and stable pricing mechanisms under private information on consumers’ reservation prices

We model the relation between an aggregator and consumers joining a coalition to reduce the risk resulting from the unpredictability of their base load demand, as a Stackelberg game formulated as a mathematical bilevel program with private information on the consumers’ reservation prices. At the upper-level of the Stackelberg game, the aggregator optimizes his daily price profile so as to reach a net targeted profit which is the maximum value guaranteeing that no consumer will leave the coalition - to contract with a conventional retailer considered here as a fixed alternative - while meeting fairness criterion imposed by the cost-sharing mechanism. At the lower-level, the consumers are asked to provide in day ahead an estimate of their base load hourly demand profile and to schedule their shiftable loads depending on the price signal sent by the aggregator. We provide algorithms that determine the unique price profile and consumer shiftable load schedules as functions of the reservation price estimates. The Stackelberg game between the aggregator and the consumers being repeated for a period of time, the aggregator has the possibility to update his estimates of the reservation prices relying on a feedback function which depends on the percentage of activated loads. A randomized algorithm for consumers’ reservation price learning based on regret minimization is provided. For four cost-sharing mechanisms such as uniform allocation, stand-alone cost, Shapley value, separable and non-separable costs, we determine the closed form of the aggregator’s optimal net targeted profit guaranteeing the stability of the coalition. We also determine conditions guaranteeing the core non-emptiness and prove that for a profit-maximizing aggregator, the stand-alone cost is always preferable to the Shapley value, which coincides with the uniform allocation. Furthermore, the optimal size of the coalition - in terms of the aggregator’s profit - can be determined analytically when the Shapley value is implemented as cost-sharing mechanism. The results are illustrated on a case study where we show that there exists an optimal net targeted profit below which the consumers energy bill is lower when joining the aggregator than with the conventional retailer. Coalition dynamics is also analyzed numerically depending on the consumer inertia in their energy supplier choice process, for each cost-sharing mechanism.     

具有质量差异的项目支付进度问题研究——以软件项目为例

目前带有惩罚结构的项目支付进度模型通常以时间或成本为激励因子,来约束承包商保证进度和节约成本,未考虑质量因素对支付进度的影响。质量是项目管理的主要目标和决定项目成败的关键因素,研究质量对项目支付进度的影响有助于激励承包商提高表现从而保证项目质量。以软件项目为例,以软件产品质量为激励因子, 分别从承包商和客户的角度构建现金流净现值最大化为目标的项目支付进度优化模型,分析承包商表现水平及风险规避对双方收益的影响。针对模型的特点设计了遗传算法和禁忌搜索算法的混合算法求解模型。最后通过算例分析表明, 质量激励因子对项目的支付进度和双方的收益均存在较大的影响,为双方协商支付进度提供决策支持。     

基于可变航速的支线集装箱船舶调度优化模型与算法

随着航运市场的竞争不断加剧和集装箱船舶大型化的发展,越来越多的航运企业选择轴-辐式航运网络模式。支线船舶调度问题作为轴-辐式航运网络的重要组成部分受到研究者的高度关注。本文研究了可变航速和经济航速两种情境下的支线船舶调度问题,同时考虑枢纽港和喂给港的取送箱时间窗限制,以航运企业运营成本最小化为目标函数建立非线性混合整数规划模型。首先使用专业的规划求解器进行小规模算例的求解,验证了模型的准确性。同时运用改进的遗传算法对大规模支线船舶优化调度模型进行求解。为了提高求解效果,进一步设计了多智能体进化算法进行求解。数值结果表明,可变航速的运营成本低于经济航速的运营成本;在算法效率方面,改进遗传算法收敛速度较快,多智能体进化算法则可以提高求解精度。     

带有固定区间的单机双代理可中断总误工问题

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.     

关于平行排序问题公平度的一个注记

利用经典的SPTgreedy算法分析了不同类机排序问题的全局公平度,证明了该算法所生成排序的公平度不超过m,并且该界为紧的.     

Methods to solve multi-skill project scheduling problem

This is a summary of the author’s PhD thesis supervised by P. Martineau and E. Néron and defended on 28 November 2006 at the Université François-Rabelais de Tours. The thesis is written in French, and is available upon request from the author. This work deals with the problem of scheduling a project. The activities of this project requires skills that may not be mastered by all persons involved. First of all, the problem is defined in the introduction part. Then we propose different methods to solve it: lower bounds in part 2, different heuristics and meta-heuristics in part 3, and finally a branch-and-bound procedure in the last part.     

Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times

This paper addresses the problem of scheduling jobs in a single machine with sequence dependent setup times in order to minimize the total tardiness with respect to job due dates. We propose variants of the GRASP metaheuristic that incorporate memory-based mechanisms for solving this problem. There are two mechanisms proposed in the literature that utilize a long-term memory composed of an elite set of high quality and sufficiently distant solutions. The first mechanism consists of extracting attributes from the elite solutions in order to influence the construction of an initial solution. The second one makes use of path relinking to connect a GRASP local minimum with a solution of the elite set, and also to connect solutions from the elite set. Reactive GRASP, which probabilistically determines the degree of randomness in the GRASP construction throughout the iterations, is also investigated. Computational tests for instances involving up to 150 jobs are reported, and the proposed method is compared with heuristic and exact methods from the literature.     

Supply chain scheduling: Sequence coordination

A critical issue in supply chain management is coordinating the decisions made by decision makers at different stages, for example a supplier and one or several manufacturers. We model this issue by assuming that both the supplier and each manufacturer have an ideal schedule, determined by their own costs and constraints. An interchange cost is incurred by the supplier or a manufacturer whenever the relative order of two jobs in its actual schedule is different from that in its ideal schedule. An intermediate storage buffer is available to resequence the jobs between the two stages. We consider the problems of finding an optimal supplier's schedule, an optimal manufacturer's schedule, and optimal schedules for both. The objective functions we consider are the minimization of total interchange cost, and of total interchange plus buffer storage cost. We describe efficient algorithms for all the supplier's and manufacturers’ problems, as well as for a special case of the joint scheduling problem. The running time of these algorithms is polynomial in both the number of jobs and the number of manufacturers. Finally, we identify conditions under which cooperation between the supplier and a manufacturer reduces their total cost.     

Stochastic scheduling in an in-forest

Consider a problem of scheduling activities of a research and development project, where precedence relations of the activities constituting the project are represented by edges of an in-forest. Each activity is characterized by two parameters: a cost for attempting that activity and a probability that attempting the activity will lead to successful completion. The problem is to find a policy for attempting activities that minimizes the expected cost incurred until termination (successful completion of the project or the first activity failure). The main result of the paper is the design of an efficient algorithm to determine an optimal sequence in which to attempt the activities; a result which is established for linear and exponential utility functions. It is also shown that, unlike the related problem with out-forest precedence relations, there need not exist an optimal policy that is based on an index-rule for determining priority of edges by evaluating their successors.