摘要:

This paper explores models and algorithms for routing and scheduling ships in a maritime transportation system. The principal thrust of this research effort is focused on the Kuwait Petroleum Corporation (KPC) Problem. This problem is of great economic significance to the State of Kuwait, whose economy has been traditionally dominated to a large extent by the oil sector, and any enhancement in the existing ad-hoc scheduling procedure has the potential for significant savings. A mixed-integer programming model for the KPC problem is constructed in this paper. The resulting mathematical formulation is rather complex to solve due to the integrality conditions and the overwhelming size of the problem for a typical demand contract scenario. Consequently, an alternate aggregate model that retains the principal features of the KPC problem is formulated. The latter model is computationally far more tractable than the initial model, and a specialized rolling horizon heuristic is developed no solve it. The proposed heuristic procedure enables us to derive solutions for practical sized problems that could not be handled by directly solving even the aggregate model. The initial formulation is solved using CPLEX-4.0-MIP capabilities for a number of relatively small-sized test cases, whereas for larger problem instances, the aggregate formulation is solved using CPLEX-4.0-MIP in concert with the developed rolling horizon heuristic, and related results are reported. An ad-hoc routing procedure that is intended to simulate the current KPC scheduling practice is also described and implemented. The results demonstrate that the proposed approach substantially improves upon the results obtained using the current scheduling practice at KPC.

ISSN:0740-817X    

DOI:10.1080/07408179908969843

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

We address the sequencing of requests in an automated storage/retrieval system with dedicated storage. We consider the block sequencing approach, where a set of storage and retrieval requests is given beforehand and no new requests come in during operation. The objective for this static problem is to find a route of minimal total travel time in which all storage and retrieval requests may be performed. The problem of sequencing a list of retrievals is equivalent to the Traveling Salesman Problem (TSP), and thusNP-hard in general. We show that the special case of sequencing under the dedicated storage policy can be solved in polynomial time. The results apply to systems with arbitrary positions of the input and output stations. Tlus generalizes the models in the literature, where only combined input/output stations are considered. Furthermore we identify a single command area in the rack. At the end we evaluate the model against heuristic procedures.

ISSN:0740-817X    

DOI:10.1080/07408179908969844

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

In this paper we describe an application of designing products and processes for supply chain management at a large electronics products manufacturer. The objective of our research project was to reduce the costs of complexity resulting from a proliferation of parts and processes in the manufacturer's supply chain. In order to perform this analysis, we developed the Supply Chain Modeling and Analysis Tool (SCMAT). SCMAT models decentralized supply chains and is less data-in tensive and yet more general than previous work in this area.

ISSN:0740-817X    

DOI:10.1080/07408179908969845

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

We consider the single item newsboy problem, where the item can be sold to different demand classes at different prices. The demands are realized sequentially over time. That is, the newsboy purchases newspapers at the beginning of the day and sells them in the morning and in the afternoon with different prices. We analyze two cases where the prices are either decreasing or increasing; the former case applies, for example, to fashion goods retailing, while the latter to airlines and hotels. In the decreasing price case, we find the optimal order quantity to maximize the expected profit with independent multiple demands. We show numerically that aggregating the multiple demands with a single average price or applying the single demand newsboy model separately to multiple demand classes may lead to large sub-optimality. In the increasing price case, we analyze a two demand class model in which a fraction of the unsatisfied lower fare demand diverts to the high fare class, thus causing dependent sales. We follow a policy of protecting the sales in the higher fare class by limiting the sales in the lower fare class. We derive both the fare allocation limit and the initial capacity, and discuss managerial implications. For both models, we give bounds on the optimal order quantity.

ISSN:0740-817X    

DOI:10.1080/07408179908969846

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

In this paper we study a two-processor scheduling problem where some tasks need to be processed by one processor, while the others have to be processed by both processors simultaneously. The objective is to minimize the total weighted completion time. We first examine the complexity of the problem, showing that it is NP-complete in the strong sense. We then derive optimality properties, and present dynamic programming algorithms, which can find optimal solutions in pseudo-polynomial time. Heuristic methods that can find approximate solutions efficiently are also proposed, and the error bounds of the approximate solutions are established. Finally, a special case is examined and a polynomial algorithm is provided. We show in the Appendix that the problem of minimizing the maximum lateness is also strongly NP-complete and that most of our approaches can be modified to solve this problem.

ISSN:0740-817X    

DOI:10.1080/07408179908969847

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

This paper addresses the problem of scheduling a nonpreemptive open shop with the objective of minimizing makespan. A neighborhood search algorithm based on the simulated annealing technique is proposed. The algorithm is tested on randomly generated problems, benchmark problems in the literature, and new hard problems generated in this paper. Computational results show that the algorithm performs well on all of the test problems. In many cases, an optimum solution is found, and in others the distance from the optimum or lower bound is quite small. Moreover, some of the benchmark problems in the literature are solved to optimality for the first time.

ISSN:0740-817X    

DOI:10.1080/07408179908969848

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

We treat the two-machine flowshop problem with the objective of minimizing the expected makespan when the jobs possess stochastic durations of arbitrary distributions. We make three contributions in this paper: (1) we propose an exact approach with exponential worst-case time complexity. We also propose approximations which are computationally modest in their requirements. Experimental results indicate that our procedure is within less than 1 % of the optimum; and (2) we provide a more elementary proof of the bounds on the project completion time based on the concepts of ‘control networks’; and (3) we extend the ‘reverse search’ procedure of Avis and Fukuda [1[ to the context of permutation schedules.

ISSN:0740-817X    

DOI:10.1080/07408179908969849

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

ISSN:0740-817X    

DOI:10.1080/07408179908969850

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor