Shop scheduling problems under precedence constraints

The paper considers a scheduling model that generalizes the well-known open shop, flow shop, and job shop models. For that model, called the super shop, we study the complexity of finding a time-optimal schedule in both preemptive and non-preemptive cases assuming that precedence constraints are imposed over the set of jobs. Two types of precedence rela-tions are considered. Most of the arising problems are proved to be NP-hard, while for some of them polynomial-time algorithms are presented.

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.

Building temporal constraints into knowledge bases for process control: an examination [Reply to author's reply]

Reply to author's reply

Non-preemptive two-machine open shop scheduling with non-availability constraints

We study a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. No preemption is allowed in the processing of any operation. The objective is to minimize the makespan. We consider approximability issues of the problem with more than one non-availability intervals and present an approximation algorithm with a worst-case ratio of 4/3 for the problem with a single non-availability interval.

Scheduling problems for parallel dedicated machines under multiple resource constraints

The paper considers scheduling problems for parallel dedicated machines subject to resource constraints. A fairly complete computational complexity classification is obtained, a number of polynomial-time algorithms are designed. For the problem with a fixed number of machines in which a job uses at most one resource of unit size a polynomial-time approximation scheme is offered.

Flow shop scheduling problems under machine–dependent precedence constraints

The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.

Single machine scheduling and due date assignment under series-parallel precedence constraints

We consider a single machine due date assignment and scheduling problem of minimizing holding costs with no tardy jobs tinder series parallel and somewhat wider class of precedence constraints as well as the properties of series-parallel graphs.

On Hamilton cycles in locally connected graphs with vertex degree constraints

It is shown that every connected, locally connected graph with the maximum vertex degree Δ(G)=5 and the minimum vertex degree δ(G)3 is fully cycle extendable. For Δ(G)4, all connected, locally connected graphs, including infinite ones, are explicitly described. The Hamilton Cycle problem for locally connected graphs with Δ(G)7 is shown to be NP-complete

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Giving credit where it's due

Discusses the entitlement to occupation rent where one party to a relationship no longer lives in the matrimonial or family home in which he/she has an interest and a right of occupation. Describes the case law illustrating that forceful exclusion of the non-occupying party is not a prerequisite to entitlement to an occupation rent. Considers the calculation of the parties' respective credits where the occupying party has made mortgage repayments since the separation and the other is entitled to an occupation rent.

Sovereign rescheduling probabilities in emerging markets: a comparison with credit rating agencies' ratings

This study estimates default probabilities of 124 emerging countries from 1981 to 2002 as a function of a set of macroeconomic and political variables. The estimated probabilities are then compared with the default rates implied by sovereign credit ratings of three major international credit rating agencies (CRAs) – Moody's Investor's Service, Standard & Poor's and Fitch Ratings. Sovereign debt default probabilities are used by investors in pricing sovereign bonds and loans as well as in determining country risk exposure. The study finds that CRAs usually underestimate the risk of sovereign debt as the sovereign credit ratings from rating agencies are usually too optimistic.

Trade credit linkages along the supply chain: evidence for the Italian textile sector

We examine the trade credit linkages among firms within a supply chain to reckon the effect of such linkages on the propagation of liquidity shocks from downstream to upstream firms. We choose a sample appropriate for this task, consisting of a large data set of Italian firms from the textile industry, a well known example of a comprehensive manufacturing cluster featuring a large number of small and specialized firms at each level of the supply chain. The results of the analysis indicate that the level of trade credit that firms provide to their suppliers is positively related to the level of trade credit granted to their clients: when the level of trade credit granted to clients divided by sales goes up by 1, the level of trade credit provided to suppliers divided by cost-of goods-sold goes up by an amount that varies between 0,22 and 0,52. Since all firms along the chain are linked by trade credit relationships, an increase in the level of trade credit granted by wholesalers generates a liquidity cascade throughout the chain. We designate the overall increase in the level of trade credit among all firms in the chain as a result of a unitary impulse in the level of trade credit granted by wholesalers as the multiplier effect of trade credit for the industry chain. We estimate such multiplier to vary between 1.28 and 2.04. We also investigate the effect of final demand on the level of trade credit sourced by firms at various levels of the chain and, in particular, whether such effect is amplified for firms further up in the chain as a result of liquidity propagation via trade credit linkages. We uncover evidence of such amplification when the links of liquidity transmission along the chain are individually modeled and estimated. An unitary increase in wholesalers’ sales is found to produce an effect on trade payables among firms at the top of the chain (i.e., Preparers and Spinners) that is more than twice as big as the corresponding effect among firms at the bottom of the chain (i.e., Wholesalers).