Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage

This paper considers a scheduling problem in two-stage hybrid flow shop, where the first stage consists of two machines formed an open shop and the other stage has only one machine. The objective is to minimize the makespan, i.e., the maximum completion time of all jobs. We first show the problem is NP-hard in the strong sense, then we present two heuristics to solve the problem. Computational experiments show that the combined algorithm of the two heuristics performs well on randomly generated problem instances.     

Choice of weights in FMA estimators under general parametric models

The choice of weights in frequentist model average estimators is an important but difficult problem. Liang et al. (2011) suggested a criterion for the choice of weight under a general parametric framework which is termed as the generalized OPT (GOPT) criterion in the present paper. However, no properties and applications of the criterion have been studied. This paper is devoted to the further investigation of the GOPT criterion. We show that how to use this criterion for comparison of some existing weights such as the smoothed AIC-based and BIC-based weights and for the choice between model averaging and model selection. Its connection to the Mallows and ordinary OPT criteria is built. The asymptotic optimality on the criterion in the case of non-random weights is also obtained. Finite sample performance of the GOPT criterion is assessed by simulations. Application to the analysis of two real data sets is presented as well.     

同时最小化具有相等加工时间的最大完工时间和加权总完工时间的序列分批排序问题(英文)

It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b ≥ n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O(n3) time.     

JOINT MODEL AND CRITERION OPTIMAL EXPERIMENT DESIGN

In this paper,a new optimal design criterion--joint model and criterion optimal de-sign criterioon is put forward. The design that is subject to this criterion satisfies many kinds of lin-ear optimal criterion and D-optimal criterion on several experiment models at the same time. Theequivalent condition of this optimal design is given. Its iterative algorithm and the algorithm cover-genee are stated.     

The NLS approximation for two dimensional deep gravity waves Dedicated to Professor Jean-Yves Chemin on the Occasion of His 60th Birthday

This article is concerned with in?nite depth gravity water waves in two space dimensions. We consider this system expressed in position-velocity potential holomorphic coordinates. Our goal is to study this problem with small wave packet data, and to show that this is well approximated by the cubic nonlinear Schr¨odinger equation(NLS) on the natural cubic time scale.     

Well-posedness and stability for an elliptic-parabolic free boundary problem modeling the growth of multi-layer tumors

In this paper we study a free boundary problem modeling the growth of multi-layer tumors. This free boundary problem contains one parabolic equation and one elliptic equation, defined on an unbounded domain in R2 of the form 0 〈 y 〈p（x,t）, where p（x,t） is an unknown function. Unlike previous works on this tumor model where unknown functions are assumed to be periodic and only elliptic equations are evolved in the model, in this paper we consider the case where unknown functions are not periodic functions and both elliptic and parabolic equations appear in the model. It turns out that this problem is more difficult to analyze rigorously. We first prove that this problem is locally well-posed in little H61der spaces. Next we investigate asymptotic behavior of the solution. By using the principle of linearized stability, we prove that if the surface tension coefficient y is larger than a threshold value y〉0, then the unique flat equilibrium is asymptotically stable provided that the constant c representing the ratio between the nutrient diffusion time and the tumor-cell doubling time is sufficiently small.     

Scheduling jobs on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties

This article addresses the problem of scheduling n jobs with a common due date on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties.We investigate the problem under the conditions that the uptimes follow an exponential distribution,and the objective measure in detail is to minimize the expected sum of the absolute deviations of completion times from the common due date.We proceed to study in two versions (the downtime follows an exponential distribution or is a constant entailed for the repeat model job),one of which is the so-called preempt- resume version,the other of which is the preempt-repeat version.Three terms of work have been done.(i)Formulations and Preliminaries.A few of necessary definitions,relations and basic facts are established.In particular,the conclusion that the expectation of the absolute deviation of the completion time about a job with deterministic processing time t from a due date is a semi-V-shape function in t has been proved.(ii) Properties of Optimal Solutions.A few characteristics of optimal solutions are established.Most importantly,the conclusion that optimal solutions possess semi-V- shape property has been proved.(iii) Algorithm.Some computing problems on searching for optimal solutions are discussed.     

A TWO-STAGE SEMI-HYBRID FLOWSHOP PROBLEM IN GRAPHICS PROCESSING

In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji consists of two tasks Ai and Bi ,and task Ai must be completed before task Bi can start. Furthermore ,task Ai can be processed on M1 for ai time units ,or on Mw for ai^J time units ,while task Bi can only be processed on M2 for bi time units. Jobs and machines are available at time zero and no preemption is allowed. The objective is to minimize the maximum job completion time. It is showed that this problem is NP-hard. And a pseudo-polynomial time optimal algorithm is presented. A polynomial time approximation algorithm with worst-case ratio 2 is also presented.     

The defocusing energy-supercritical Hartree equation

In this paper,we study the global well-posedness and scattering problem for the energysupercritical Hartree equation iut+Δu.(|x|.γ.|u|2)u=0 with γ4 in dimension d γ.We prove that if the solution u is apriorily bounded in the critical Sobolev space,that is,u ∈Lt∞(I;Hxsc(Rd)) with sc:= γ/2.11,then u is global and scatters.The impetus to consider this problem stems from a series of recent works for the energy-supercritical nonlinear wave equation(NLW) and nonlinear Schrdinger equation(NLS).We utilize the strategy derived from concentration compactness ideas to show that the proof of the global well-posedness and scattering is reduced to disprove the existence of three scenarios:finite time blowup;soliton-like solution and low to high frequency cascade.Making use of the No-waste Duhamel formula,we deduce that the energy of the finite time blow-up solution is zero and so get a contradiction.Finally,we adopt the double Duhamel trick,the interaction Morawetz estimate and interpolation to kill the last two scenarios.     

Inventory sharing in integrated network design and inventory optimization with low-demand parts

Service Parts Logistics (SPL) problems induce strong interaction between network design and inventory stocking due to high costs and low demands of parts and response time based service requirements. These pressures motivate the inventory sharing practice among stocking facilities. We incorporate inventory sharing effects within a simplified version of the integrated SPL problem, capturing the sharing fill rates in 2-facility inventory sharing pools. The problem decides which facilities in which pools should be stocked and how the demand should be allocated to stocked facilities, given full inventory sharing between the facilities within each pool so as to minimize the total facility, inventory and transportation costs subject to a time-based service level constraint. Our analysis for the single pool problem leads us to model this otherwise non-linear integer optimization problem as a modified version of the binary knapsack problem. Our numerical results show that a greedy heuristic for a network of 100 facilities is on average within 0.12% of the optimal solution. Furthermore, we observe that a greater degree of sharing occurs when a large amount of customer demands are located in the area overlapping the time windows of both facilities in 2-facility pools.     

A Heuristic Solution Procedure to Minimize Makespan on a Single Machine with Non-linear Cost Functions

We consider the static single-facility scheduling problem where the processing times of jobs are a nondecreasing and differentiable function of their starting (waiting) times and the objective is to minimize the total elapsed time (makespan) in which all jobs complete their processing. We give a criterion for optimality of two jobs to be scheduled next to each other, and based on this criterion we propose a heuristic algorithm to solve the problem. The effectiveness of the algorithm is empirically evaluated for quadratic and exponential cost functions. In the quadratic case it is compared with the static heuristic algorithm proposed by Gupta and Gupta.     

A simulation optimization approach for a two-echelon inventory system with service level constraints

In this paper, we present a simulation optimization algorithm for solving the two-echelon constrained inventory problem. The goal is to determine the optimal setting of stocking levels to minimize the total inventory investment costs while satisfying the expected response time targets for each field depot. The proposed algorithm is more adaptive than ordinary optimization algorithms, and can be applied to any multi-item multi-echelon inventory system, where the cost structure and service level function resemble what we assume. Empirical studies are performed to compare the efficiency of the proposed algorithms with other existing simulation algorithms.     

A three-machine permutation flow-shop problem with minimum makespan on the second machine

In this paper, we consider a three-machine permutation flow-shop scheduling problem where the criterion is to minimize the total completion time without idle times subject to the minimum makespan on the second machine. This problem is NP-hard while each of the objective functions alone can be optimized in polynomial time. We develop a branch-and-bound algorithm with effective branching rules and dominance properties which help to reduce the search space. By our computational experiments, the branch-and-bound algorithm is comparable to a recent mixed integer programming solver and, for some kinds of problem instances, the branch-and-bound algorithm outperforms the solver. On the other hand, the computational result would indicate that the hierarchical scheduling problems are essentially hard in both theoretical and computational points of view.     

Single Machine Group Scheduling with Two Ordered Criteria

The problem of scheduling jobs on a single machine is considered. It is assumed that the jobs are classified into several groups and the jobs of the same group have to be processed contiguously. A sequence independent set-up time is incurred between each two consecutively scheduled groups. A schedule is specified by a sequence for the groups and a sequence for the jobs in each group. The quality of a schedule is measured by two critera ordered by their relative importance. The objective is to minimize the maximum cost, the secondary criterion, subject to the schedule is optimal with respect to total weighted completion time, the primary criterion. A polynomial time algorithm is presented to solve this bicriterion group scheduling problem. It is shown that this algorithm can also be modified to solve the single machine group scheduling problem with several ordered maximum cost criteria and arbitrary precedence constraints.     

具有交易费用和马氏调制的均值-方差组合选择

研究了均值-方差准则下,最优投资组合选择问题.投资者为了增加财富它可以在金融市场上投资.金融市场由一个无风险资产和n个带跳的风险资产组成,并假设金融市场具有马氏调制,买卖风险资产时,考虑交易费用.目标是,在终值财富的均值等于d的限制下,使终值财富的方差最小,即均值-方差组合选择问题.应用随机控制的理论解决该问题,获得了最优的投资策略和有效边界.     

The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan

This paper addresses the problem of scheduling unit-time operations with integral and non-negative time delay considerations on a two-machine open-shop environment. The criterion to minimize is the makespan. Two well solvable cases and two approximation algorithms, with their worst-case analyses, are presented.     

A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times

This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods.     

Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects

In this article, we study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup time of each job is past-sequence-dependent. The objective is to minimize the total completion time. We show that there exists a polynomial time solution for the proposed problem. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.     

A multi-period machine assignment problem

In this paper, a multi-period assignment problem is studied that arises as part of a weekly planning problem at mail processing and distribution centers. These facilities contain a wide variety of automation equipment that is used to cancel, sort, and sequence the mail. The input to the problem is an equipment schedule that indicates the number of machines required for each job or operation during the day. This result is then post-processed by solving a multi-period assignment problem to determine the sequence of operations for each machine. Two criteria are used for this purpose. The first is to minimize the number of startups, and the second is to minimize the number of machines used per operation.The problem is modeled as a 0–1 integer program that can be solved in polynomial time when only the first criterion is considered. To find solutions in general, a two-stage heuristic is developed that always obtains the minimum number of startups, but not necessarily the minimum number of machines per operation. In a comparative study, high quality solutions were routinely provided by the heuristic in negligible time when compared to a commercial branch-and-bound code (Xpress). For most hard instances, the branch-and-bound code was not able to even find continuous solutions within acceptable time limits.