Metaheuristics for the mixed shop scheduling problem

In this paper, three metaheuristics are proposed for solving a class of job shop, open shop, and mixed shop scheduling problems. We evaluate the performance of the proposed algorithms by means of a set of Lawrence’s benchmark instances for the job shop problem, a set of randomly generated instances for the open shop problem, and a combined job shop and open shop test data for the mixed shop problem. The computational results show that the proposed algorithms perform extremely well on all these three types of shop scheduling problems. The results also reveal that the mixed shop problem is relatively easier to solve than the job shop problem due to the fact that the scheduling procedure becomes more flexible by the inclusion of more open shop jobs in the mixed shop.

Complexity of mixed shop scheduling problems: A survey

We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be processed in arbitrary order (as in the open shop). The main attention is devoted to establishing the boundary between polynomially solvable and NP-hard problems. When the number of operations per job is unlimited, we focus on problems with a fixed number of jobs.

Metaheuristics for minimizing the makespan of the dynamic shop scheduling problem

For the shop scheduling problems such as flow-shop, job-shop, open-shop, mixed-shop, and group-shop, most research focuses on optimizing the makespan under static conditions and does not take into consideration dynamic disturbances such as machine breakdown and new job arrivals. We regard the shop scheduling problem under static conditions as the static shop scheduling problem, while the shop scheduling problem with dynamic disturbances as the dynamic shop scheduling problem. In this paper, we analyze the characteristics of the dynamic shop scheduling problem when machine breakdown and new job arrivals occur, and present a framework to model the dynamic shop scheduling problem as a static group-shop-type scheduling problem. Using the proposed framework, we apply a metaheuristic proposed for solving the static shop scheduling problem to a number of dynamic shop scheduling benchmark problems. The results show that the metaheuristic methodology which has been successfully applied to the static shop scheduling problems can also be applied to solve the dynamic shop scheduling problem efficiently.

A fast tabu search algorithm for the group shop scheduling problem

Three types of shop scheduling problems, the flow shop, the job shop and the open shop scheduling problems, have been widely studied in the literature. However, very few articles address the group shop scheduling problem introduced in 1997, which is a general formulation that covers the three above mentioned shop scheduling problems and the mixed shop scheduling problem. In this paper, we apply tabu search to the group shop scheduling problem and evaluate the performance of the algorithm on a set of benchmark problems. The computational results show that our tabu search algorithm is typically more efficient and faster than the other methods proposed in the literature. Furthermore, the proposed tabu search method has found some new best solutions of the benchmark instances.

Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

The paper deals with the determination of an optimal schedule for the so-called mixed shop problem when the makespan has to be minimized. In such a problem, some jobs have fixed machine orders (as in the job-shop), while the operations of the other jobs may be processed in arbitrary order (as in the open-shop). We prove binary NP-hardness of the preemptive problem with three machines and three jobs (two jobs have fixed machine orders and one may have an arbitrary machine order). We answer all other remaining open questions on the complexity status of mixed-shop problems with the makespan criterion by presenting different polynomial and pseudopolynomial algorithms.

Benchmark generation algorithm for stochastic mixed model assembly shop simulation and optimization

The Operations Research (OR) community have defined many deterministic manufacturing control problems mainly focused on scheduling. Well-defined benchmark problems provide a mechanism for communication of the effectiveness of different optimization algorithms. Manufacturing problems within industry are stochastic and complex. Common features of these problems include: variable demand, machine part specific breakdown patterns, part machine specific process durations, continuous production, Finished Goods Inventory (FGI) buffers, bottleneck machines and limited production capacity. Discrete Event Simulation (DES) is a commonly used tool for studying manufacturing systems of realistic complexity. There are few reports of detail-rich benchmark problems for use within the simulation optimization community that are as complex as those faced by production managers. This work details an algorithm that can be used to create single and multistage production control problems. The reported software implementation of the algorithm generates text files in eXtensible Markup Language (XML) format that are easily edited and understood as well as being cross-platform compatible. The distribution and acceptance of benchmark problems generated with the algorithm would enable researchers working on simulation and optimization of manufacturing problems to effectively communicate results to benefit the field in general.

Evidence for insertional codemixing: mixed compounds and French nominal groups in Brussels Dutch

In this paper we analyse mixed compounds, such as legume+winkel ‘vegetable shop, greengrocery’ and winter+paletot ‘winter coat’ which contain a French and a Dutch element, and French nominal groups, such as carte d’identité ‘identity card’, and journal parlé ‘radio news’, which bilingual speakers from Brussels frequently insert into Brussels Dutch utterances. Using Muysken’s (2000) typology of bilingual speech, we claim that the mixed compounds and the nominal groups display the characteristics of insertional code-mixing. In addition, some evidence for the existence of a continuum between borrowing and code-switching can be obtained from these examples. As the multimorphemic units that are inserted into Dutch are neither single words, nor full constituents, their status in the lexicon raises interesting issues for researchers interested in the interface between syntax and the lexicon (see also Backus 2003). We try to argue that nominal groups such as carte d’identité and journal parlé are probably best seen as lexical templates or constructional idioms (Booij, 2002b). The insertion of French constructional idioms in Brussels Dutch represents an innovation in the lexical patterns that are available to speakers of this language, which is highly relevant for theories of language change.

New dimeric supramolecular structure of mixed (phthalocyaninato)(porphyrinato)-europium(III) sandwiches : preparation and spectroscopic characteristics

The mixed double-decker Eu\[Pc(15C5)4](TPP) (1) was obtained by base-catalysed tetramerisation of 4,5-dicyanobenzo-15-crown-5 using the half-sandwich complex Eu(TPP)(acac) (acac = acetylacetonate), generated in situ, as the template. For comparative studies, the mixed triple-decker complexes Eu2\[Pc(15C5)4](TPP)2 (2) and Eu2\[Pc(15C5)4]2(TPP) (3) were also synthesised by the raise-by-one-story method. These mixed ring sandwich complexes were characterised by various spectroscopic methods. Up to four one-electron oxidations and two one-electron reductions were revealed by cyclic voltammetry (CV) and differential pulse voltammetry (DPV). As shown by electronic absorption and infrared spectroscopy, supramolecular dimers (SM1 and SM3) were formed from the corresponding double-decker 1 and triple-decker 3 in the presence of potassium ions in MeOH/CHCl3.

Raman spectroscopic characteristics of phthalocyanine and naphthalocyanine in sandwich-type phthalocyaninato and porphyrinato rare earth complexes Part 5. – Raman spectroscopic characteristics of naphthalocyanine in mixed [tetrakis(4-tert-butylphenyl)porphyrinato]-(naphthalocyaninato) rare earth double-deckers

Raman spectra were recorded in the range 400–1800 cm−1 for a series of 15 mixed \[tetrakis(4-tert-butylphenyl)porphyrinato](2,3-naphthalocyaninato) rare earth double-deckers M(TBPP)(Nc) (M = Y; La–Lu except Pm) using laser excitation at 632.8 and 785 nm. Comparisons with bis(naphthalocyaninato) rare earth counterparts reveal that the vibrations of the metallonaphthalocyanine M(Nc) fragment dominate the Raman features of M(TBPP)(Nc). When excited with radiation of 632.8 nm, the most intense vibration appears at about 1595 cm−1, due to the naphthalene stretching. These complexes exhibit the marker Raman band for Nc•− as a medium-intense band in the range 1496–1507 cm−1, attributed to the coupling of pyrrole and aza stretching, while the marker Raman band of Nc2− in intermediate-valence Ce(TBPP)(Nc) appears as a strong band at 1493 cm−1 and is due to the isoindole stretchings. By contrast, when excited with radiation of 785 nm that is in close resonance with the main Q absorption band of the naphthalocyanine ligand, the ring radial vibrations at ca 680 and 735 cm−1 for MIII(TBPP)(Nc) are selectively intensified and are the most intense bands. For the cerium double-decker, the most intense vibration also acting as the marker Raman band of Nc2− appears at 1497 cm−1 with contributions from both pyrrole CC and aza CN stretches. The same vibrational modes show weak to medium intensity scattering at 1506–1509 cm−1 for MIII(TBPP)(Nc) and this is the marker Raman band of Nc•− when thus excited. The scatterings due to the Nc breathings, ring radial vibration, aza group stretchings, naphthalene stretchings, benzoisoindole stretchings and the coupling of pyrrole CC and aza CN stretchings in MIII(TBPP)(Nc) are all slightly blue shifted along with the decrease in rare earth ionic radius, confirming the effects of increased ring–ring interactions on the Raman characteristics of naphthalocyanine in the mixed ring double-deckers.