Jian Yang  Xiangtong Qi  Gang Yu 《海军后勤学研究》2005,52(5):420-442

We study the problem of recovering a production plan after a disruption, where the disruption may be caused by incidents such as power failure, market change, machine breakdown, supply shortage, worker no‐show, and others. The new recovery plan we seek after has to not only suit the changed environment brought about by the disruption, but also be close to the initial plan so as not to cause too much customer unsatisfaction or inconvenience for current‐stage and downstream operations. For the general‐cost case, we propose a dynamic programming method for the problem. For the convex‐cost case, a general problem which involves both cost and demand disruptions can be solved by considering the cost disruption first and then the demand disruption. We find that a pure demand disruption is easy to handle; and for a pure cost disruption, we propose a greedy method which is provably efficient. Our computational studies also reveal insights that will be helpful to managing disruptions in production planning. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.  相似文献   

    

Hui Liu  Maurice Queyranne  David Simchi‐Levi 《海军后勤学研究》2005,52(3):232-242

We consider the nonpermutation flow shop problem with release dates, with the objective of minimizing the sum of the weighted completion times on the final machine. Since the problem is NP‐hard, we focus on the analysis of the performance of several approximation algorithms, all of which are related to the classical Weighted Shortest Processing Time Among Available Jobs heuristic. In particular, we perform a probabilistic analysis and prove that two online heuristics and one offline heuristic are asymptotically optimal. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.  相似文献   

    

Irina N. Lushchakova  Alan J. Soper  Vitaly A. Strusevich 《海军后勤学研究》2009,56(1):1-18

We consider the two‐machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a ‐approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009  相似文献   

    

Frank Meisel 《海军后勤学研究》2011,58(7):619-636

The quay crane scheduling problem consists of scheduling tasks for loading and unloading containers on cranes that are assigned to a vessel for its service. This article introduces a new approach for quay crane scheduling, where the availability of cranes at a vessel is restricted to certain time windows. The problem is of practical relevance, because container terminal operators frequently redeploy cranes among vessels to speed up the service of high‐priority vessels while serving low‐priority vessels casually. This article provides a mathematical formulation of the problem and a tree‐search‐based heuristic solution method. A computational investigation on a large set of test instances is used to evaluate the performance of the heuristic and to identify the impact of differently structured crane time windows on the achievable vessel handling time. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011  相似文献   

    

Chi To Ng  Mikhail Yakovlevich Kovalyov  Tai Chiu Edwin Cheng 《海军后勤学研究》2008,55(3):194-199

  相似文献   

    

Guohua Wan  Xiangtong Qi 《海军后勤学研究》2010,57(2):159-171

In this article, we study a class of new scheduling models where time slot costs have to be taken into consideration. In such models, processing a job will incur certain cost which is determined by the time slots occupied by the job in a schedule. The models apply when operational costs vary over time. The objective of the scheduling models is to minimize the total time slot costs plus a traditional scheduling performance measure. We consider the following performance measures: total completion time, maximum lateness/tardiness, total weighted number of tardy jobs, and total tardiness. We prove the intractability of the models under general parameters and provide polynomial‐time algorithms for special cases with non‐increasing time slot costs.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010  相似文献   

    

Lixin Tang  Feng Li  Jiyin Liu 《海军后勤学研究》2015,62(5):416-433

Motivated by some practical applications, we study a new integrated loading and transportation scheduling problem. Given a set of jobs, a single crane is available to load jobs, one by one, onto semitrailers with a given capacity. Loaded semitrailers are assigned to tractors for transportation tasks. Subject to limited resources (crane, semitrailers, and tractors), the problem is to determine (1) an assignment of jobs to semitrailers for loading tasks, (2) a sequence for the crane to load jobs onto semitrailers, (3) an assignment of loaded semitrailers to tractors for transportation tasks, and (4) a transportation schedule of assigned tractors such that the completion time of the last transportation task is minimized. We first formulate the problem as a mixed integer linear programming model (MILPM) and prove that the problem is strongly NP‐hard. Then, optimality properties are provided which are useful in establishing an improved MILPM and designing solution algorithms. We develop a constructive heuristic, two LP‐based heuristics, and a recovering beam search heuristic to solve this problem. An improved procedure for solutions by heuristics is also presented. Furthermore, two branch‐and‐bound (B&B) algorithms with two different lower bounds are developed to solve the problem to optimality. Finally, computational experiments using both real data and randomly generated data demonstrate that our heuristics are highly efficient and effective. In terms of computational time and the number of instances solved to optimality in a time limit, the B&B algorithms are better than solving the MILPM. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 416–433, 2015  相似文献   

    

Sina Ansari  Seyed M. R. Iravani  Qifeng Shao 《海军后勤学研究》2019,66(5):367-392

Existing models in multistage service systems assume full information on the state of downstream stages. In this paper, we investigate how much the lack of such information impacts jobs' waiting time in a two‐stage system with two types of jobs at the first stage. The goal is to find the optimal control policy for the server at the first stage to switch between type‐1 and type‐2 jobs, while minimizing the long‐run average number of jobs in the system. We identify control policies and corresponding conditions under which having no or partial information, the system can still capture the most benefit of having full information.  相似文献   

    

Gur Mosheiov  Daniel Oron 《海军后勤学研究》2004,51(7):1005-1017

In due‐window assignment problems, jobs completed within a designated time interval are regarded as being on time, whereas early and tardy jobs are penalized. The objective is to determine the location and size of the due‐window, as well as the job schedule. We address a common due‐window assignment problem on parallel identical machines with unit processing time jobs. We show that the number of candidate values for the optimal due‐window starting time and for the optimal due‐window completion time are bounded by 2. We also prove that the starting time of the first job on each of the machines is either 0 or 1, thus introducing a fairly simple, constant‐time solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004  相似文献   

    

Luigi Moccia  Jean‐Franois Cordeau  Manlio Gaudioso  Gilbert Laporte 《海军后勤学研究》2006,53(1):45-59

The quay crane scheduling problem consists of determining a sequence of unloading and loading movements for cranes assigned to a vessel in order to minimize the vessel completion time as well as the crane idle times. Idle times originate from interferences between cranes since these roll on the same rails and a minimum safety distance must be maintained between them. The productivity of container terminals is often measured in terms of the time necessary to load and unload vessels by quay cranes, which are the most important and expensive equipment used in ports. We formulate the quay crane scheduling problem as a vehicle routing problem with side constraints, including precedence relationships between vertices. For small size instances our formulation can be solved by CPLEX. For larger ones we have developed a branch‐and‐cut algorithm incorporating several families of valid inequalities, which exploit the precedence constraints between vertices. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006  相似文献