Enhanced adjacent extreme-point search and tabu search for the minimum concave-cost uncapacitated transshipment problem

Practicable methods for optimising concave-cast, uncapacitated transshipment networks are non exact. In this paper, one such effective method, that of adjacent extreme point search, is further developed to enhance its overall computational efficiency. The enhanced search algorithm is then imbedded in a tabu search scheme which proved capable of finding better solutions, by a wide margin in some instances. Another tabu search scheme, somewhat inferior in terms of solution quality but computationally more efficient, is also developed to provide an alternative solution vehicle for larger networks. Results of extensive computational testing are included.


Approximate queueing models for capacitated multi-stage inventory systems under base-stock control
Avşar, Zeynep Müge (Elsevier BV, 2014-07-01)
A queueing analysis is presented for base-stock controlled multi-stage production-inventory systems with capacity constraints. The exact queueing model is approximated by replacing some state-dependent conditional probabilities (that are used to express the transition rates) by constants. Two recursive algorithms (each with several variants) are developed for analysis of the steady-state performance. It is analytically shown that one of these algorithms is equivalent to the existing approximations given in ...
A conic quadratic formulation for a class of convex congestion functions in network flow problems
Gürel, Sinan (Elsevier BV, 2011-06-01)
In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be effici...
Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria
Ozlen, M.; Azizoğlu, Meral (Informa UK Limited, 2011-01-01)
In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the follo...
Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed
Azizoğlu, Meral; Koksalan, SK (Informa UK Limited, 2003-06-01)
We address the bicriteria problem of minimizing the number of tardy jobs and maximum earliness on a single machine where machine idle time is allowed. We show that the problem of minimizing the number of tardy jobs while maximum earliness is kept at its minimum value of zero is polynomially solvable. We present polynomial time algorithms for the maximum earliness problem subject to no tardy jobs and the maximum earliness problem for a given set of tardy jobs. Finally, we discuss the use of the latter algori...
In this paper we consider the job shop scheduling problem under a discrete non-renewable resource constraint. We assume that jobs have arbitrary processing times and resource requirements and there is a unit supply of the resource at each time period. We develop an approximation algorithm for this problem and empirically test its effectiveness in finding the minimum makespan schedules.
Citation Formats
C. F. Bazlamaçcı, “Enhanced adjacent extreme-point search and tabu search for the minimum concave-cost uncapacitated transshipment problem,” JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, pp. 1150–1165, 1996, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/57079.