Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment

The paper considers the single machine due date assignment and scheduling problems with n jobs in which the due dates are to be obtained from the processing times by adding a positive slack q. A schedule is feasible if there are no tardy jobs and the job sequence respects given precedence constraints. The value of q is chosen so as to minimize a function ϕ(F,q) which is non-decreasing in each of its arguments, where F is a certain non-decreasing earliness penalty function. Once q is chosen or fixed, the corresponding scheduling problem is to find a feasible schedule with the minimum value of function F. In the case of arbitrary precedence constraints the problems under consideration are shown to be NP-hard in the strong sense even for F being total earliness. If the precedence constraints are defined by a series-parallel graph, both scheduling and due date assignment problems are proved solvable in time, provided that F is either the sum of linear functions or the sum of exponential functions. The running time of the algorithms can be reduced to if the jobs are independent. Scope and purpose We consider the single machine due date assignment and scheduling problems and design fast algorithms for their solution under a wide range of assumptions. The problems under consideration arise in production planning when the management is faced with a problem of setting the realistic due dates for a number of orders. The due dates of the orders are determined by increasing the time needed for their fulfillment by a common positive slack. If the slack is set to be large enough, the due dates can be easily maintained, thereby producing a good image of the firm. This, however, may result in the substantial holding cost of the finished products before they are brought to the customer. The objective is to explore the trade-off between the size of the slack and the arising holding costs for the early orders.

Dynamic mesh partitioning and load-balancing for parallel computational mechanics codes

In this Chapter we discuss the load-balancing issues arising in parallel mesh based computational mechanics codes for which the processor loading changes during the run. We briefly touch on geometric repartitioning ideas and then focus on different ways of using a graph both to solve the load-balancing problem and the optimisation problem, both locally and globally. We also briefly discuss whether repartitioning is always valid. Sample illustrative results are presented and we conclude that repartitioning is an attractive option if the load changes are not too dramatic and that there is a certain trade-off between partition quality and volume of data that the underlying application needs to migrate.

Preemptive scheduling on uniform parallel machines with controllable job processing times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.

Financing of SME's: an asset side story

The main sources of financing for small and medium sized enterprises (SMEs) are equity (internally generated cash), trade credit paid on time, long and short term bank credits, delayed payment on trade credit and other debt. The marginal costs of each financing instrument are driven by asymmetric information (cost of gathering and analysing information) and transactions costs associated with non-payment (costs of collecting and selling collateral). According to the Pecking Order Theory, firms will choose the cheapest source in terms of cost. In the case of the static trade-off theory, firms choose finance so that the marginal costs across financing sources are all equal, thus an additional Euro of financing is obtained from all the sources whereas under the Pecking Order Theory the source is determined by how far down the Pecking Order the firm is presently located. In this paper, we argue that both of these theories miss the point that the marginal costs are dependent of the use of the funds, and the asset side of the balance sheet primarily determines the financing source for an additional Euro. An empirical analysis on a unique dataset of Portuguese SME's confirms that the composition of the asset side of the balance sheet has an impact of the type of financing used and the Pecking Order Theory and the traditional Static Trade-off theory are rejected.