Chance constrained programming models for refinery short-term crude oil scheduling problem

The main objective of this work is to put forward chance constrained mixed-integer nonlinear stochastic and fuzzy programming models for refinery short-term crude oil scheduling problem under demands uncertainty of distillation units. The scheduling problem studied has characteristics of discrete events and continuous events coexistence, multistage, multiproduct, nonlinear, uncertainty and large scale. At first, the two models are transformed into their equivalent stochastic and fuzzy mixed-integer linear programming (MILP) models by using the method of Quesada and Grossmann [I. Quesada, I E. Grossmann, Global optimization of bilinear process networks with multicomponent flows, Comput. Chem. Eng. 19 (12) (1995) 1219–1242], respectively. After that, the stochastic equivalent model is converted into its deterministic MILP model through probabilistic theory. The fuzzy equivalent model is transformed into its crisp MILP model relies on the fuzzy theory presented by Liu and Iwamura [B.D. Liu, K. Iwamura, Chance constrained programming with fuzzy parameters, Fuzzy Sets Syst. 94 (2) (1998) 227–237] for the first time in this area. Finally, the two crisp MILP models are solved in LINGO 8.0 based on scheduling time discretization. A case study which has 267 continuous variables, 68 binary variables and 320 constraints is effectively solved with the solution approaches proposed.     

排课问题分组优化决策中的CourseRank

时间表(T im etab ling)问题是NP-完全的,因此很难寻求一个有效的整体优化算法.分组作为重要的优化策略,可以将课程按优先等级逐次分组,每组再采用组合优化方法.通常认为课程的规模是优先等级的决定性因素.然而选课的模式允许学生在一定的范围内选择课程,这就使得课程的关联关系更复杂.该文将课程的关联关系描述为一个M arkov链,进而给出了课程优先度(CourseR ank)的概念.通过对清华大学2002年度学生选课数据的分析和计算,结果表明课程的规模仍然是重要的因素,但并不完全是决定性的.     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

Scheduling interfering job sets on parallel machines

We consider bicriteria scheduling on identical parallel machines in a nontraditional context: jobs belong to two disjoint sets, and each set has a different criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal is to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT–LPT–SPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are designed to exploit the problem structure and generate a set of non-dominated solutions. In the genetic algorithm we use a special encoding scheme and also a unique strategy – based on the properties of a non-dominated solution – to ensure that all parts of the non-dominated front are explored. The heuristic and the genetic algorithm are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide high solution quality and are computationally efficient. The heuristics proposed also have the potential to be generalized for the problem of interfering job sets involving other bicriteria pairs.     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

Retail store scheduling for profit

In spite of its tremendous economic significance, the problem of sales staff schedule optimization for retail stores has received relatively scant attention. Current approaches typically attempt to minimize payroll costs by closely fitting a staffing curve derived from exogenous sales forecasts, oblivious to the ability of additional staff to (sometimes) positively impact sales. In contrast, this paper frames the retail scheduling problem in terms of operating profit maximization, explicitly recognizing the dual role of sales employees as sources of revenues as well as generators of operating costs. We introduce a flexible stochastic model of retail store sales, estimated from store-specific historical data, that can account for the impact of all known sales drivers, including the number of scheduled staff, and provide an accurate sales forecast at a high intra-day resolution. We also present solution techniques based on mixed-integer (MIP) and constraint programming (CP) to efficiently solve the complex mixed integer non-linear scheduling (MINLP) problem with a profit-maximization objective. The proposed approach allows solving full weekly schedules to optimality, or near-optimality with a very small gap. On a case-study with a medium-sized retail chain, this integrated forecasting–scheduling methodology yields significant projected net profit increases on the order of 2–3% compared to baseline schedules.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

A better semi-online algorithm for Q3/s1 = s2≤ s3/Cmin with the known largest size

This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 < s1 = s2 = r ≤ t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max{2, (3s+6)/(s+6) } is presented. We also show the lower bound is at least max{2, (3s)/(s+6)}. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.     

Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized precedence constraints (minimal time-lags) have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized.We calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.     

Scheduling in Multiclass Networks with Deterministic Service Times

We consider general feed-forward networks of queues with deterministic service times and arbitrary arrival processes. There are holding costs at each queue, idling may or may not be permitted, and servers may fail. We partially characterize the optimal policy and give conditions under which lower priority should be given to jobs that would be delayed later in the network if they were processed now.