Exact algorithms for scheduling multiple families of jobs on parallel machines

In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 823–840, 2003.     

雷达干扰资源一对多分配方法

在对雷达干扰资源分配的一般优化模型和求解算法进行分析的基础上,从提高资源利用效率的角度出发,提出了目标雷达分群思想,并建立了一种新的基于一对多策略的雷达干扰资源分配模型,通过对目标雷达群的一对一分配实现对单部雷达的一对多分配.最后,对该模型中一些关键性问题进行了探讨,如任务整合、新任务参数确定、任务优先级排序、干扰机位置部署以及单目标雷达群干扰效益评估等.     

区域联合作战装备保障任务分配模型

现代信息化战争是体系与体系的对抗,区域作战联合装备保障成为信息化条件下装备保障的主要方式,实施科学正确的装备保障指挥,进行保障任务分配对于提高保障效益具有非常重要的意义。通过区域作战装备保障任务的特点,依据区域保障要求建立了包括转场时间在内和不同作战方向上作战单元的重要程度不同的装备保障任务分配模型,保证了重要方向上最晚完成保障任务的作战单元保障时间最短和非重要方向上最晚完成保障任务的作战单元保障时间最短。最后,应用遗传算法给出了区域联合作战装备保障任务分配模型的求解方法和步骤,具有一定的科学性和实用性。     

A logistics scheduling model: Inventory cost reduction by batching

Logistics scheduling refers to the problems where the decisions of job scheduling and transportation are integrated in a single framework. In this paper, we discuss a logistics scheduling model where the raw material is delivered to the shop in batches. By making the batching and scheduling decisions simultaneously, the total inventory and batch setup cost can be reduced. We study different models on this issue, present complexity analysis and optimal algorithms, and conduct computational experiments. Some managerial insights are observed. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Machine scheduling with pickup and delivery

The coordination of production, supply, and distribution is an important issue in logistics and operations management. This paper develops and analyzes a single‐machine scheduling model that incorporates the scheduling of jobs and the pickup and delivery arrangements of the materials and finished jobs. In this model, there is a capacitated pickup and delivery vehicle that travels between the machine and the storage area, and the objective is to minimize the makespan of the schedule. The problem is strongly NP‐hard in general but is solvable in polynomial time when the job processing sequence is predetermined. An efficient heuristic is developed for the general problem. The effectiveness of the heuristic is studied both analytically and computationally. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

C2组织结构设计:平台-任务关系设计

以联合作战战役为例建立作战平台和任务模型,对C2(Command and Control)组织结构设计中平台-任务关系设计问题分析了传统多维动态列表规划算法(Multidimensional Dynamic List Scheduling,MDLS)在解决作战平台资源调度(平台-任务分配)问题的不足,提出了在平台-任务分配过程中采用任务选择平台组、平台选择任务以及两者选择冲突消除改进的MDLS算法,以解决MDLS算法的不足,并对不同方法的结果进行了比较.     

Relaxed sequencing games have a nonempty core

We study sequencing situations with a fixed initial order and linear cost functions. Cost savings can be obtained by rearranging jobs. Next to finding an optimal order, an additional issue is formed by the division of these savings. Cooperative game theory studies this issue. A common assumption states that cooperation between players is restricted to groups that are connected according to the initial order. The value of disconnected groups is defined additively over their connected components. In this paper we allow players in disconnected coalitions to switch places as long as they do not hurt the players not in the coalition under consideration. The resulting games are called relaxed sequencing games. Although they have been studied before, no general results on stable profit divisions have been derived so far. In this paper we prove that relaxed sequencing games have a nonempty core, i.e., they all have stable profit divisions. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006