Manuel A Juncal
email: majuncales@uvigo.es

Sylvie Bourquin

Laurent Beccaletto

José B Diez

Borja Cascales

New sedimentological and palynological data from the Permian and Triassic series of the Sancerre-Couy core, Paris Basin, France 

Keywords: Palynostratigraphy, Depositional environment, Middle-Upper Triassic, Ladinian, Carnian, Rhaetian

A new description and sampling campaign of the Sancerre-Couy core has been achieved to reconstruct the evolution of the depositional environments of the Permian and Triassic series and the palynological evolution of the Permian to Lower Jurassic series. High-resolution sequence stratigraphy of the Permian and Triassic series of the Paris Basin, based on well-log A c c e p t e d M a n u s c r i p t analysis, is used to determine seven progradational-retrogradational cycles in the Permian and twelve cycles in the Triassic. Out of the 54 samples collected from the Sancerre-Couy-1 core, only 23 were palynologically productive. Based on the taxonomic composition, four palynological assemblages are distinguished, three of which have been described in previous studies. These three classical palynological assemblages of the Sancerre-Couy-1 core are documented in detail for the first time in this present study. The description of the new assemblage and its correlation can be used to reassess the previously assigned ages:

assemblage SC-1 is late Ladinian in age, SC-2 is of the Ladinian-Carnian transition, SC-3 is early Carnian in age, and SC-4 is of late Rhaetian age whereas it had previously been assigned a Hettangian age.

Introduction

Late Carboniferous (Stephanian) to Permian basins cropping out in and around the presentday French Variscan basement were initiated during the latest extensional stages of the Variscan orogeny (Echtler and Malavieille, 1990;[START_REF] Burg | Syn-to post-thickening extension in the Variscan Belt of Western Europe: modes and structural consequences[END_REF][START_REF] Praeg | Diachronous Variscan late-orogenic collapse as a response to multiple detachments; a view from the internides in France to the foreland in the Irish Sea[END_REF]; Fig. 1(A)).

These basins are also identified in the subsurface beneath the Meso-Cenozoic sedimentary cover of the Paris Basin, but without any clear tectono-sedimentary framework [START_REF] Mascle | Géologie pétrolière des basins permiens français. Comparaison avec les bassins permiens du Nord de l'Europe[END_REF]Perrodon and Zabek, 1990;Delmas et al., 2002). More recently, the geometry and A c c e p t e d M a n u s c r i p t structural evolution of the Stephano-Permian basins located in the south-western part of the Paris Basin have been studied using seismic data [START_REF] Beccaletto | Structural evolution and sedimentary record of the Stephano-Permian basins occurring beneath the Mesozoic sedimentary cover in the southwestern Paris basin (France)[END_REF]. However, the lack of core data means that it was neither possible to provide a precise description of the depositional environment and age assessment nor their sedimentary succession. The Triassic deposits then overly the Permian deposits through an angular unconformity, as seen in the western part of the Germanic Basin (i.e., more or less at the place of the present-day Paris Basin; [START_REF] Bourquin | Lower Triassic sequence stratigraphy of the western part of the Germanic Basin (west of Black Forest): fluvial system evolution through time and space[END_REF].

The Sancerre-Couy-1 core was drilled in 1986 in the south-western part of the Paris Basin, 30 km west of the city of Bourges [START_REF] Chantraine | Forage scientifique de Sancerre-Couy (Cher): Synthèse d'études 1986-1992[END_REF]Figs. 1(B), 2). The primary target of this scientific well was the study of the PBMA (Paris Basin Magnetic Anomaly), a major magnetic anomaly situated in the basement of the Paris Basin; unfortunately, the deep source rock of the PBMA was not reached. The Sancerre-Couy-1 core cut through a preserved Permian to Jurassic sedimentary succession. So far, only scarce data have been published from this well regarding the Permian [START_REF] Orszag-Sperber | Forage scientifique de Sancerre-Couy (Cher): Synthèse d'études 1986-1992[END_REF] or Triassic sedimentary evolution [START_REF] Adloff | Le Trias du forage de Sancerre-Couy: la trangression triasique est le témoin d'un haut niveau marin ladinien[END_REF]. This paper presents the results of a new description and sampling campaign carried out to restudy the Sancerre-Couy-1 core. We specify precise changes in the depositional environment of the Permian to Early Jurassic succession and characterise the palynological content.

Geological setting

Paris Basin

The Paris Basin, located in northern France, is a low subsidence Meso-Cenozoic intracratonic sedimentary basin set up on a Variscan substratum that includes late Carboniferous-Permian basins (Fig. 1). The latter were identified using subsurface geophysics and well data;

A c c e p t e d M a n u s c r i p t generally speaking, there is no consensus with regard to their extension and geological evolution [START_REF] Mégnien | Tectonogenèse du Bassin de Paris: étapes de l'évolution du bassin[END_REF][START_REF] Mascle | Géologie pétrolière des basins permiens français. Comparaison avec les bassins permiens du Nord de l'Europe[END_REF]Perrodon and Zabeck, 1990;[START_REF] Autran | Gravity and magnetic expression of terranes in France and their correlation beneath overstep sequences[END_REF]Guillocheau et al., 2000). A recent study describes the palaeogeographic extent of the Stephano-Permian basins beneath the Mesozoic series in the south-western Paris Basin and delineates how the sediments were deposited during two successive tectonic phases [START_REF] Beccaletto | Structural evolution and sedimentary record of the Stephano-Permian basins occurring beneath the Mesozoic sedimentary cover in the southwestern Paris basin (France)[END_REF]. However, the lack of high-resolution core data in the Paris Basin makes it difficult to provide a precise description of the depositional environment and to date the Palaeozoic sedimentary deposits.

South-east of the Sancerre-Couy core, several isolated (late Carboniferous-Permian subbasins also outcrop over the deformed magmatic and metamorphic rocks of the French Massif Central (Aumance, Autun, Decize-La Machine, Blanzy-Le Creusot, Fig. 1(B); [START_REF] Marteau | Le bassin permo-carbonifère d'Autun; Stratigraphie, sédimentologie et aspects structuraux[END_REF]Vallé, 1986;[START_REF] Paquette | Le bassin de Bourbon l'Archambault. Synthèse géologique des bassins permiens français[END_REF][START_REF] Roger | Palynological investigations in the Carnian of the Cave del Predil area (Julian Alps, NE Italy)[END_REF]. Recently, new accurate CA-ID-TIMS U-Pb zircon ages recorded from tonsteins have been used to date the Gzelian-Permian transition in the Autun sub-basin [START_REF] Pellenard | Highprecision U-Pb zircon ages for explosive volcanism calibrating the NW European continental Autunian stratotype[END_REF].

Within the Paris Basin, the Triassic succession progressively onlaps on the pre-Triassic unconformity [START_REF] Bourquin | Lower Triassic sequence stratigraphy of the western part of the Germanic Basin (west of Black Forest): fluvial system evolution through time and space[END_REF]. During the Early and Middle Triassic, the Paris Basin corresponds to the western part of the Germanic Basin [START_REF] Bourquin | The Permian-Triassic transition and the beginning of the Mesozoic sedimentation at the Western peri-Tethyan domain scale: palaeogeographic maps and geodynamic implications[END_REF] and become an independent basin from the middle Carnian (Late Triassic) onward (Bourquin andGuillocheau, 1993, 1996). The Triassic evolution of the Paris Basin is well known based on sequence stratigraphy correlations using well-log, core and outcrop data. These have been used to reconstruct isopach and palaeoenvironmental maps [START_REF] Bourquin | High-resolution sequence stratigraphy A c c e p t e d M a n u s c r i p t in the Triassic series of the Paris Basin: geodynamic implications[END_REF][START_REF] Bourquin | Three-dimensional accommodation analysis of the Keuper of the Paris Basin: discrimination between tectonics, eustasy, and sediment supply in the stratigraphic record[END_REF][START_REF] Bourquin | The Permian-Triassic transition and the beginning of the Mesozoic sedimentation at the Western peri-Tethyan domain scale: palaeogeographic maps and geodynamic implications[END_REF]. However, biostratigraphic ages of the sedimentary succession are very scarce and documented primarily from outcrop data in the eastern part of the basin.

A c c e p t e d M a n u s c r i p t

The Sancerre-Couy-1 well

The Sancerre-Couy-1 well was cored and well-logged in the southwestern part of the Paris Basin (Fig. 1(B)). The fully cored well starts in the Callovian sediments outcropping in this part of the basin. The base of the core reached the amphibolite basement at a depth of 3500 m.

The basement, composed of metamorphic rocks and starting at a depth of 941.65 m, is overlain by the Palaeozoic sedimentary series [START_REF] Lorenz | Le Jurassique[END_REF]. The latter is composed of volcanoclastic deposits until a depth of 925.35 m, attributed to the Stephanian [START_REF] Chantraine | Forage scientifique de Sancerre-Couy (Cher): Synthèse d'études 1986-1992[END_REF]. Trachyandesites sampled at the bottom of the Stephanian unit yield an Ar-Ar age of 301 Ma [START_REF] Costa | Datation par la méthode Ar-Ar de matériel magmatique et métamorphique paléozoïque provenant du forage de Couy-Sancerre (Programme GPF)[END_REF]. The core is deposited at the BRGM in Orleans, France.

The Stephanian volcaniclastic unit is overlain by Permian fluvio-lacustrine deposits with an angular discordance [START_REF] Lorenz | Le Jurassique[END_REF]. These sediments are attributed to the late Permian based on the presence of several Darwinulacea ostracods [START_REF] Orszag-Sperber | Forage scientifique de Sancerre-Couy (Cher): Synthèse d'études 1986-1992[END_REF].

The Permian sediments are overlain by the Triassic succession (from 809.8 m to 559.6 m deep). [START_REF] Courel | La transgression triasique en France centrale; témoin d'un haut niveau marin ladinien; données nouvelles du sondage de Sancerre-Couy (Cher, France)[END_REF] distinguishes the following Triassic formations: fluvial deposits at the base ('Grès argileux de base' Fm.), a shallow lagoon-marine deposits with tidal influences ('Grès infra-anhydritique' Fm.) and evaporitic deposits ('Argile à anhydrite' Fm., 'Grès supra-anhydritique' Fm., and 'Argile de Chalain' Fm.) (Fig. 2). Sporomorph assemblages indicate a late Ladinian to Carnian age for the basal part of the Argile à anhydrite Fm. [START_REF] Adloff | Le Trias[END_REF][START_REF] Adloff | Le Trias du forage de Sancerre-Couy: la trangression triasique est le témoin d'un haut niveau marin ladinien[END_REF]. In comparison with the Massif Central area, [START_REF] Courel | La transgression triasique en France centrale; témoin d'un haut niveau marin ladinien; données nouvelles du sondage de Sancerre-Couy (Cher, France)[END_REF] consider the Grès infra-anhydritique Fm. as the maximum coastal onlap onto the late Variscan palaeoreliefs.

The first levels, considered as Jurassic (559.6 m; Fig. 2), are composed of coarse sandstones, with coal fragments and bivalves, progressively overlain by carbonate deposits around 542 m [START_REF] Lorenz | Le Jurassique du forage de Sancerre-Couy[END_REF]Fig. 2). These sandstone and carbonate deposits were attributed to the [START_REF] Lorenz | Le Jurassique du forage de Sancerre-Couy[END_REF].

Material and methods

The Sancerre-Couy-1 core was used to establish a detailed sedimentological log from the basement (925.35 m) up to the supposed Hettangian interval (553 m;Chanteraine et al., 1992;[START_REF] Lorenz | Le Jurassique du forage de Sancerre-Couy[END_REF] at a 1:50 scale. Fifty-four samples (PC-01 to PC-54) were collected from the Sancerre-Couy-1 core; the levels with the most organic matter and finest grain size for palynological studies were selected. Twenty-three of the 54 collected samples are productive. Samples were processed in the laboratory of the Geosciences Department at the University of Vigo in Spain, using standard palynological HCl-HF-HCl techniques. The samples were processed by first adding HCl and HF to remove the carbonate and silicate minerals. A dispersing agent was subsequently added to facilitate filtering. The residue was mounted on a glass slide and observed under a Nikon Bio-Rad confocal microscope at the CACTI Labs at the University of Vigo.

Depositional environment of the Permian and Triassic series and palynological analysis

The Permian alluvial fan to shallow lake series

In the Sancerre-Couy-1 core, the Permian sediments are mainly composed of siltstones with sandstones and few conglomerates (Table 1). The base of the series, from 925 to 894 m, is A c c e p t e d M a n u s c r i p t mainly composed of conglomerates and sandstones with interbedded fine-grained facies. The conglomerates, which mainly display an erosive base, are constituted of very poorly sorted gravel to cobble-size quartz, feldspar, and silty, sandy and volcanic clasts. They are composed of massive matrix-(silt to sand) or clast-supported facies (Gmm and Gmc facies, respectively;

Table 1) typical of debris or a hyper-concentrated flow process [START_REF] Postma | Depositional architecture and facies of river and fan deltas: a synthesis[END_REF][START_REF] Mehdi | The Geology of Fluvial Deposits[END_REF].

In several cases, the conglomerates are clast-supported with either horizontal bedding (Gh facies; Table 1) or planar cross-stratification (Gp facies; Table 1), typical of a streamflow process [START_REF] Postma | Depositional architecture and facies of river and fan deltas: a synthesis[END_REF][START_REF] Mehdi | The Geology of Fluvial Deposits[END_REF]. The sandstones are composed of massive fine to medium grains (Sm facies) that are sometimes bioturbated (Smb facies; Table 1), which is typical for subaerial hyper-concentrated density flows or subaqueous high-density turbidity currents [START_REF] Lowe | Sediment gravity flows: II. Depositional models with special reference to the deposits of high-density turbidity currents[END_REF][START_REF] Mulder | The physical character of subaqueous sedimentary density flows and their deposits[END_REF]. Features of a tractive current such as current ripples (Sr facies; Table 1) or trough cross-stratification (St facies; Table 1) are observed. These indicate streamflow processes [START_REF] Postma | Depositional architecture and facies of river and fan deltas: a synthesis[END_REF][START_REF] Mehdi | The Geology of Fluvial Deposits[END_REF]. This facies association corresponds to an alluvial-fan environment [START_REF] Blair | Alluvial fan processes and forms[END_REF] that is dominated by debris flows (sediment gravity flows and catastrophic fluid gravity flows). It is possible to distinguish a proximal alluvial fan facies association composed of a gravity flow process (Gmm, Gmc, and Sm facies) and a distal alluvial fan facies association with the development of streamflow processes (Gp, Gh, Sr, Sm, and St facies). The predominantly fine-grained sediments consist of massive or laminated silts (F facies) or are composed of a heterolithic facies (Fl facies; Table 1), which are sometimes bioturbated (Fb and Flb facies, monospecific for the Scoyenia type). Sometimes massive or finely laminated dolomite (Dm facies; Table 1) or oolitic facies (Fo facies; Table 1) are associated with fine-grained facies, indicating a constant water level, sometimes with high energy. Some cm-scale levels with dolomite nodules may indicate the development of palaeosols (Dn facies; Table 1). The finegrained facies association is typical of floodplains (F and Fl facies) or shallow lakes (Fb, Flb, A c c e p t e d M a n u s c r i p t Fo, and Dm facies). Consequently, the lower part of the Permian succession of the Sancerre-Couy-1 core shows three retrogradational-progradational sequences (noted PI, PII and PIII; Fig. 3). These sequences are characterised by an increasing lacustrine influence with decreasing alluvial fan deposits towards the top (from PI to PIII). The retrogradational trend is marked by alluvial fan deposits, which evolve vertically to distal alluvial fans or floodplain and shallow lake environments. The progradational trend is marked by a change from lake to floodplain environments sometimes with palaeosol development.

From 894 to 811 m, the Permian succession is characterised by the dominance of the above described fine-grained facies. Thin sandstone beds (cm to dm in thickness) are intercalated into the fine-grained facies. They occur as massive beds (Sm facies; Table 1) with horizontal lamination (Sh facies; Table 1), current (Sr facies; Table 1) or wave ripples (Sw facies; Table 1), and even with trough cross-stratification in rare cases (St facies; Table 1). They are frequently bioturbated (Smb and Srb facies; Table 1). This facies association is typical of subaqueous environments with frequent episodes of fluvial input, i.e., a shallow lake environment in semi-arid climate conditions as evidenced by carbonate facies (Dm and Fn facies; Table 1; [START_REF] Hasiotis | Continental trace fossils[END_REF][START_REF] Hasiotis | Climatic controls on continental track fossils[END_REF]. Consequently, four retrogradationalprogradational sequences (denoted as PIV to PVII; Fig. 3) are observed, with well-developed progradational trends towards proximal lacustrine depositional environments except for sequence PV, where the progradational trend ends with a floodplain, a distal alluvial fan environment, and probably a palaeosol (Fn facies; Table 1).

The Permian series shows a general trend from alluvial fan to shallow lake deposits.

Unfortunately, all relevant palynological samples are barren (PC-01 to PC-05; Fig. 3).

The fluvio-lacustrine and sebkha Triassic series

A c c e p t e d M a n u s c r i p t

Depositional environment and retrogradational-progradational cycles

The Triassic series studied here is composed of siliciclastic and anhydritic materials with very few dolomitic deposits (Fig. 4). The lower part, from 811 to 792 m, is composed of conglomerates and sandstones with few silty levels (Fl facies; Table 1) that are primarily bioturbated (monospecific for the Scoyenia type Flb facies; Table 1). The conglomerates are composed of poorly-sorted gravel to pebbles, either massive matrix-supported (coarse sand) or clast-supported (Gmm and Gmc facies, respectively; Table 1), sometimes with crossbedding stratification (Gtp facies; Table 1). The sandstones are fine-to coarse-grained, either massive (Sm facies; Table 1) or displaying horizontal (Sh facies; Table 1) or cross-bedding stratification (St and Stp facies; Table 1), and are sometimes intensely bioturbated (monospecific for the Scoyenia type Sb, Shb, and Stb facies; Table 1). Locally, dolomite nodules may indicate the development of palaeosols (Dn facies). These deposits are mainly organised in normally graded sequences from conglomerates to fine bioturbated siltstones (cm to dm in thickness), typical of braided alluvial fan deposits within a shallow lake environment [START_REF] Bourquin | High-resolution sequence stratigraphy of an alluvial fan -fan delta environment: stratigraphic and geodynamic implications -Example of the Chaunoy Sandstones, Keuper of the Paris Basin[END_REF]. The sediments of this depositional environment develop up-section into either silt and clay dominated facies (F facies; Table 1), and sometimes bioturbated (Fb facies; Table 1) or heterolithic facies (Fl and Flb facies; Table 1). The latter are composed of silt and clay with few very fine-to fine-grained sandstone beds (mm to cm in thickness), with currents and more rarely oscillatory ripples (Fl facies) that are frequently bioturbated (Flb facies). Clays may contain some anhydrite nodules (Fa facies; Table1). The depositional environment is attributed to a shallow lake environment with few fluvial inputs, which increases progressively from 780 to 733 m. This first sequence (denoted as TI; Fig. 4) records a retrogradational trend with an evolution from a braided alluvial fan within a shallow lake environment, where the maximum retrogradation is located close to 780 m. The progradational trend is marked by an increase in sediment supply that ends with a distal A c c e p t e d M a n u s c r i p t alluvial fan deposit within a playa lake, as evidenced by the presence of a higher frequency of anhydrite intervals (A and Fa facies; Table 1).

From 732 to 720 m, the second sequence (denoted as TII; Fig. 4) only displays a retrogradational trend from a braided alluvial fan (Gmc, Gt, Gh, St, Sb, and Flb facies association) to silty clay deposits (F facies) that are sometimes bioturbated (Fb facies) and include anhydrite nodule levels (A and Fa facies). These fine-grained facies, with cm-scale beds of anhydritic nodules and few siliciclastic inputs, are typical of anhydrite sebkha (Bourquin andGuillocheau, 1993, 1996).

From 720 to 692 m, the overlying siliciclastic deposits are finer and thinner, reflecting more distal fan-delta deposits (sand sheet, Fl, Sr, St, Fl, and Flb facies association). They are associated with anhydrite sebkha deposits (A facies association) with increased black silty clays contents (F facies), rich in palynomorphs (until 705 m). This facies association reflects two sequences (denoted TIII and TIV; Fig. 4) that record a retrogradational and progradational trend where the maximum flooding episode is marked by black silty clays.

The fifth sequence (denoted as TV; Fig. 4) starts with few sand sheet deposits within a playa lake (Flb facies, with current and oscillatory ripples, associated with anhydritic nodules, A facies). The maximum flooding event is also marked by black clay. The progradational trend characterises an increase in the anhydritic level content associated with red clay, and ends with a well-developed, 1 m-thick anhydritic bed.

The sixth sequence (denoted as TVI; Fig. 4) displays red clay and anhydritic nodules that are increasingly less developed toward the top, attesting to a retrogradational trend. The progradational trend shows a fluvial sand sheet within playa-lake environment (Flb and Shb facies).

The seventh to eleventh sequences (denoted as TVII to TXII; Fig. 4) mainly record the

Palynological analysis of the Triassic series

The first four samples (PC-06 to PC-09; Figs. 4,5) collected in the Triassic levels did not yield any palynomorphs. The 23 productive samples are grouped into four palynological assemblages based on their taxonomical composition, three of which were described in previous studies: SC-1 is studied as the "second assemblage" in [START_REF] Adloff | Le Trias[END_REF] and [START_REF] Courel | La transgression triasique en France centrale; témoin d'un haut niveau marin ladinien; données nouvelles du sondage de Sancerre-Couy (Cher, France)[END_REF], SC-2 as the "first assemblage" in [START_REF] Adloff | Le Trias[END_REF], and SC-4 is studied in [START_REF] Lorenz | Le Jurassique[END_REF]. In addition, a new association (SC-3) is described from samples PC-39, PC-40 and PC-41. The studies mentioned above show preliminary species lists without any pictures. The present study allowed us not only to confirm the majority of the previous identifications, but also to identify a new palynological assemblage stratigraphically well constrained to the 698.45-697.45 m interval, and to reinterpret the 559.25-553 m levels previously attributed to the Hettangian (Early Jurassic; Fig. 5).

We identified the following taxa in the first palynological assemblage (SC-1: samples PC-

New stratigraphic attribution to the green sandstones

Starting from 559 m, the distal alluvial fan deposits are well developed with Sh facies underlain by mud clast and coal fragments. This stratigraphic interval is characterised by another retrogradational trend and has been attributed to the Lower Liassic without any biostratigraphic constraint. Only the occurrence of a bioclastic limestone with Gryphaea, starting at a depth of 508.2 m, suggests the Sinemurian stage, because of the regional appearance of this fossil [START_REF] Lorenz | Le Jurassique du forage de Sancerre-Couy[END_REF].

The following taxa were identified for the palynological assemblage SC-4 (Samples PC-46 to PC-54; Fig. 11

Discussion

The Sancerre-Couy core can be used to describe the depositional environment of the Permian to Jurassic series. The Permian succession is divided into seven progradationalretrogradational cycles, showing a general evolution from alluvial fan to shallow lake deposits (Fig. 3). Unfortunately, all relevant palynological samples were barren and cannot specify the age of this series, which is considered as Permian [START_REF] Orszag-Sperber | Forage scientifique de Sancerre-Couy (Cher): Synthèse d'études 1986-1992[END_REF]. The Permian succession probably corresponds to the upper Permian based on a seismic line correlation showing similar series further west [START_REF] Beccaletto | Structural evolution and sedimentary record of the Stephano-Permian basins occurring beneath the Mesozoic sedimentary cover in the southwestern Paris basin (France)[END_REF].

The Triassic cycles defined from the sedimentary evolution (Fig. 3) have been compared with those of [START_REF] Bourquin | Three-dimensional accommodation analysis of the Keuper of the Paris Basin: discrimination between tectonics, eustasy, and sediment supply in the stratigraphic record[END_REF] defined from previously published well-log data and sequence stratigraphy (Fig. 12). The SC-1, SC-2 and SC-3 associations correspond to the end of the progradation trend of the major Anisian-Carnian cycle [START_REF] Bourquin | Lower Triassic sequence stratigraphy of the western part of the Germanic Basin (west of Black Forest): fluvial system evolution through time and space[END_REF]. The SC-1 and SC-2 association (Fig. 3) corresponds to the Ladinian-lower Carnian cycle (Fig. 12), which is A c c e p t e d M a n u s c r i p t the lateral equivalent of the Erfurt Fm. in the eastern part of the Paris Basin [START_REF] Bourquin | Three-dimensional accommodation analysis of the Keuper of the Paris Basin: discrimination between tectonics, eustasy, and sediment supply in the stratigraphic record[END_REF]. The SC-2 and SC-3 associations (Fig. 3) belong to the minor lower-Carnian cycle (Fig. 12), which is a lateral equivalent of the 'Marnes irisées inférieures' Fm. in the eastern part of the basin [START_REF] Bourquin | Three-dimensional accommodation analysis of the Keuper of the Paris Basin: discrimination between tectonics, eustasy, and sediment supply in the stratigraphic record[END_REF]. [START_REF] Courel | La transgression triasique en France centrale; témoin d'un haut niveau marin ladinien; données nouvelles du sondage de Sancerre-Couy (Cher, France)[END_REF][START_REF] Courel | Sequence Stratigraphy of the Triassic series on the western Peri-Tethyan margin (France, Switzerland)[END_REF] add Leiotriletes sp. and Porcellispora longdonensis to this list of taxa, and the assemblage was assigned to the late Ladinian due to a correlation with the palynological associations described from the Mâconnais Region, France [START_REF] Adloff | Étude palynologique dans le Mésozoïque de base de la bordure NE du Massif Central français. 7ème réunion annuelle des Sciences de la terre[END_REF], Jura Department, France [START_REF] Adloff | Zonations palynostratigraphiques dans les séries triasiques traversées par les sondages dans le Jura et le Bas-Dauphiné[END_REF], Largentière Basin, Ardèche, France (Doubinger and Adloff, 1977), and the Monte San Giorgio, Southern Alps, Switzerland [START_REF] Scheuring | Mikrofloren aus den Meridelkalken des Monte San Giorgio (Kanton Tessin)[END_REF]. The SC-1 assemblage corresponds in age to the Camerosporites secatus-Enzonalasporites vigens phase (Van der Eem, 1983), the Heliosaccus dimorphus zone from Orłowska-Zwolińska (1983,1985,1988) and [START_REF] Kürschner | Triassic palynology of central and northwestern Europe: a review of palynofloral diversity patterns and biostratigraphic subdivisions[END_REF], and the TrS-F Zone (Protrachyceras archelaus-Frankites regoledanus Zone) from [START_REF] Hochuli | Palynological zonation and particulate organic matter of the Middle Triassic of the Southern Alps (Seceda and Val Gola-Margon sections, Northern Italy)[END_REF]. Brugman, 1981;Van der Eem, 1983;Brugman et al., 1994;Roghi, 2004;[START_REF] Cirilli | Upper Triassic-lowermost Jurassic palynology and palynostratigraphy: a review[END_REF][START_REF] Kürschner | Triassic palynology of central and northwestern Europe: a review of palynofloral diversity patterns and biostratigraphic subdivisions[END_REF]. The first appearance of Patinasporites densus corresponds to the base of the early Carnian Enzonalasporites vigens-Patinasporites densus phase of Van der Eem (1983) and is associated with the first appearance of Vallasporites ignacii (Visscher and Brugman, 1981;Van der Eem, 1983;Fisher and Dunay, 1984;[START_REF] Blendinger | Palynostratigraphy of the late Ladinian and Carnian in the Southeastern Dolomites[END_REF][START_REF] Hochuli | Triassic biostratigraphy of the Barents Sea area[END_REF][START_REF] Hochuli | Palynological zonation and particulate organic matter of the Middle Triassic of the Southern Alps (Seceda and Val Gola-Margon sections, Northern Italy)[END_REF]Roghi, 2004;[START_REF] Cirilli | Upper Triassic-lowermost Jurassic palynology and palynostratigraphy: a review[END_REF][START_REF] Kürschner | Triassic palynology of central and northwestern Europe: a review of palynofloral diversity patterns and biostratigraphic subdivisions[END_REF]. SC-2 corresponds to the "first assemblage" of [START_REF] Adloff | Le Trias[END_REF], collected from the 699.45-697.45 m interval (unspecified levels), and composed of Ovalipollis pseudoalatus, Vallasporites ignacii, Camerosporites secatus, Paracirculina quadruplicis, and Patinasporites densus. [START_REF] Adloff | Le Trias[END_REF] compare their assemblage with the Jura borehole assemblages (association A5; [START_REF] Adloff | Zonations palynostratigraphiques dans les séries triasiques traversées par les sondages dans le Jura et le Bas-Dauphiné[END_REF] and the ammonite levels of the Austrian Alps (Dunay and Fisher, 1978), attributing it a Carnian age. 1983) and from the Cordevolian to the early Tuvalian (Visscher and Brugman, 1981;[START_REF] Litwin | Preliminary palynological zonation of the Chinle Formation, southwestern USA, and its correlation to the Newark Supergroup (eastern USA)[END_REF][START_REF] Hochuli | Palynological zonation and particulate organic matter of the Middle Triassic of the Southern Alps (Seceda and Val Gola-Margon sections, Northern Italy)[END_REF]Roghi, 2004;Medhi et al., 2009;[START_REF] Roghi | Palynological correlation of Carnian humid pulses throughout western Tethys: Palaeogeography[END_REF].

Additionally, Aulisporites astigmosus is characteristic of the early Carnian palynological assemblages (Dunay and Fisher, 1978;Orłowska-Zwolińska, 1983;[START_REF] Hochuli | Mesozoic and Cenozoic sequence chronostratigraphic framework of European basins[END_REF]Fijałkowska-Mader, 1999;[START_REF] Kirichkova | The problem of correlation between Triassic continental sequences of Southern Germany, the Timan-Pechora region and Eastern Urals[END_REF]Medhi et al., 2009, Fijałkowska-Mader, 1999). The co-occurrence of Lagenella martinii and Aulisporites astigmosus have been described from the Dupliciporites continuus assemblage of the Conzen and Tor Fm. (Roghi, 2004), as well as the early Carnian Tr3 (Black Dolostones) and Tr4 (Middle Gypsum) units of the Rheouis Fm. (Medhi et al., 2009). The association is also comparable with those of the Astigmosus zone, described in Poland (Orłowska-Zwolińska, 1983;Fijałkowska-Mader, 1999) and from European epicontinental areas (Dunay and Fisher, 1978;[START_REF] Brugman | Permian-Triassic palynology[END_REF]Medhi et al., 2009). Moreover, this association is present in many other parts of Europe related with the Carnian Pluvial Event which determined a humid climatic perturbation over a large area of the Northern Hemisphere [START_REF] Roghi | Palynological correlation of Carnian humid pulses throughout western Tethys: Palaeogeography[END_REF].

The SC-4 assemblage is late Rhaetian in age due to the presence of Carnisporites spiniger, Classopollis meyeriana, Convolutispora klukiforma, Kraeuselisporites (= Heliosporites) reissingeri, Ovalipollis pseudoalatus and Taurocusporites verrucatus, as well as the dinoflagellates Dapcodinium priscum and Rhaetogonyalax rhaetica. Taxonomically, this assemblage is similar to the one shown in the upper part of the Lower Member (middle Rhaetian) in the Rhaetian Fm. of the Lodève Basin, France (Courtinat and Piriou, 2002). It resembles the RG Subzone (Rhaetian) in the Kendelbachgraben section, Austria [START_REF] Morbey | A scheme of palynologically defined concurrent-range zones and subzones for the Triassic Rhaetian Stage (sensu lato)[END_REF], and the B association (upper part of the early Rhaetian) from [START_REF] Adloff | Étude palynologique du Rhétien et de l'Hettangien de cinq sondages situés dans les environs de Mersch (Luxembourg)[END_REF]. Assemblage SC-4 is located at stratigraphical levels (559-553 m) equivalent to the base of the 555.8-515.80 m interval studied in Lorenz et al. (1978) as Cerebropollenites pseudomassulae, inferring that these samples are found in the basal part of the Hettangian. However, Taugourdeau (in Lorenz et al., 1987) provides evidence for the possibility of carrying out a more precise study as Rhaetian material may be found at the bottom of this interval. Later, [START_REF] Lorenz | Le Jurassique du forage de Sancerre-Couy[END_REF] discarded this hypothesis and shortened the palynological interval to 555.25-542.55 m.

The high prevalence of Classopollis spp. together with Carnisporites spiniger, Deltoidospora spp., Kraeuselisporites (= Heliosporites) reissingeri, and Ovalipollis pseudoalatus, together with the occurrence of the dinoflagellates Dapcodinium priscum and Rhaetogonyalax rhaetica, is observed in the SAB3 zone from the upper part of the Lilstock Fm., St. Audrie's Bay [START_REF] Bonis | Milankovitch-scale palynological turnover across the Triassic-Jurassic transition at St. Audrie's Bay, SW UK[END_REF][START_REF] Lindström | Palynofloral patterns of terrestrial ecosystem change during the end-Triassic event -a review[END_REF]Lindström et al., 2017). The SAB3 zone (Bonis et al., 2010) is considered to represent the "recovery flora" during the end-Triassic event [START_REF] Lindström | Palynofloral patterns of terrestrial ecosystem change during the end-Triassic event -a review[END_REF]. The last appearance of Ovalipollis pseudoalatus together with the first appearance of Kraeuselisporites (= Heliosporites) reissingeri in some parts of Europe (Hochalplgraben, Austria: [START_REF] Bonis | A detailed palynological study of the Triassic-Jurassic transition in key sections of the Eiberg Basin (Northern Calcareous Alps, Austria)[END_REF]St Audrie's Bay, United Kingdom: Bonis et al., 2010;Kuhjoch, Austria: Hillebrandt et al., 2013;Stenlille, Denmark: Lindström, 2016;Lindström et al., 2017) may be characteristic of this late Rhaetian event.

The coexistence of the microplankton Dapcodinium priscum and Rhaetogonyalax rhaetica has been also recorded in other studies: in the Kendelbachgraben section, Austria (Rhaetian age; [START_REF] Morbey | A scheme of palynologically defined concurrent-range zones and subzones for the Triassic Rhaetian Stage (sensu lato)[END_REF], the Brigadier Fm. in the North West Shelf of Australia [START_REF] Backhouse | Palynological zonation and correlation of the latest Triassic, Northern Carnarvon Basin[END_REF], the Rhaetian Fm. of the Lodève Basin, France (middle Rhaetian; Courtinat and Piriou, 2002), the Northern Calcareous Alps, Austria (latest Rhaetian in presented by [START_REF] Courel | La transgression triasique en France centrale; témoin d'un haut niveau marin ladinien; données nouvelles du sondage de Sancerre-Couy (Cher, France)[END_REF] and [START_REF] Lorenz | Le Jurassique du forage de Sancerre-Couy[END_REF]. The new records allow: (i) a better definition of the age of two assemblages (lower and upper, equivalent to PC-1 and PC-2); (ii) the definition of a new palynostratigraphic assemblage (PC-3), belonging to the 698.45-697.45 m interval; and (iii) the reinterpretation of the 559.25-553 m levels (PC-4; [START_REF] Lorenz | Le Jurassique du forage de Sancerre-Couy[END_REF]) previously attributed to the Hettangian (Early Jurassic).

The different ages attributed for some cycles in our study confirm the hypothesis given in [START_REF] Bourquin | Three-dimensional accommodation analysis of the Keuper of the Paris Basin: discrimination between tectonics, eustasy, and sediment supply in the stratigraphic record[END_REF]. The PC-1, PC-2 and PC-3 palynological associations correspond to the end of the progradation trend for the major Anisian-Carnian cycle [START_REF] Bourquin | Lower Triassic sequence stratigraphy of the western part of the Germanic Basin (west of Black Forest): fluvial system evolution through time and space[END_REF]. The PC-1 and PC-2 association corresponds to the Ladinian-lower Carnian cycle, which is the lateral equivalent of the Erfurt Fm. in the eastern part of the Paris Basin [START_REF] Bourquin | Three-dimensional accommodation analysis of the Keuper of the Paris Basin: discrimination between tectonics, eustasy, and sediment supply in the stratigraphic record[END_REF]. The PC-2 and PC-3 association corresponds to the minor lower-Carnian cycle, which is a lateral equivalent of the 'Marnes irisées inférieures' Fm. in the eastern part of the basin [START_REF] Bourquin | Three-dimensional accommodation analysis of the Keuper of the Paris Basin: discrimination between tectonics, eustasy, and sediment supply in the stratigraphic record[END_REF]. The PC-4 assemblage suggests a late Rhaetian age and corresponds to the SAB3 zone which is considered to represent the "recovery flora" during the end-Triassic event [START_REF] Lindström | Palynofloral patterns of terrestrial ecosystem change during the end-Triassic event -a review[END_REF]. Consequently, the Rhaetian-Hettangian boundary in the Sancerre-Couy-1 core should be located in the lower part of the interval between 553 and 508. Gely, J.P., Lorenz, J., 1991. Analyse séquentielle du Jurassique du forage de Couy. Comptes Rendus de l'Académie des Sciences de Paris 313, 247-353. Guillocheau, F., Robin, C., Allemand, P., Bourquin, S., Brault, N., Dromart, G., Friedenberg, R., Garcia, J.P., Gaulier, J.M, Gaumet, F., Grosdoy B., Manot, F., Le Strat, P., Mettraux, M. Nalpas, T., Prijac, P., Rigollet C., Serrano, O., Grandjean, G., 2000. Meso-cenozoic geodynamic evolution of the Paris Basin: 3D stratigraphic constraints. Geodinamica Acta 13,. Klaus, 1964. 3. Triadispora suspecta Scheuring, 1970. 4. Triadispora verrucata (Schulz) [START_REF] Paracirculina | [END_REF]. 5. Triadispora plicata Klaus, 1964. 6. Alisporites grauvogeli Klaus, 1964. 7. Alisporites opii Daugherty, 1941. 8. Triadispora epigona Klaus, 1964. 9. Illinites chitonoides Klaus, 1964. 10. Ovalipollis pseudoalatus (Thiergart) [START_REF] Thiergart) Schuurman | Ovalipollis pseudoalatus[END_REF]. 11. Staurosaccites quadrifidus Dolby, 1976. Scale bar: 10 µm. Chordasporites singulichorda Klaus, 1960. 3. Quadraeculina anellaeformis Maljavkina, 1949. 4. Samaropollenites speciosus Goubin, 1965. 5. Brachysaccus neomundanus (Leschik) Mädler, 1964. 6. Camerosporites secatus Leschik, 1956. 7. Porcellispora longdonensis (Clarke) [START_REF] Paracirculina | [END_REF]emend. Morbey, 1975. 8. Duplicisporites granulatus (Leschik) [START_REF] Paracirculina | [END_REF]. 9. Duplicisporites sp. 10. Paracirculina scurrilis Scheuring, 1970. 11. Camerosporites secatus Leschik, 1956. 9. Porcellispora longdonensis (Clarke) [START_REF] Paracirculina | [END_REF]emend. Morbey, 1975. 10. Praecirculina granifer (Leschik) Klaus, 1960. 11. Paracirculina scurrilis Scheuring, 1970. 12. Patinasporites densus Leschik, 1955. 13. Vallasporites ignacii Leschik, 1956. 14. Quadraeculina anellaeformis Maljavkina, 1949. 15. Ovalipollis pseudoalatus (Thiergart) Schuurman, 1976. Scale bar: 10 µm. Duplicisporites granulatus (Leschik) [START_REF] Paracirculina | [END_REF]. 7. Vallasporites ignacii Leschik, 1956. 8. Aulisporites astigmosus (Leschik) Klaus, 1960. 9. Camerosporites secatus Leschik, 1956. 10. Calamospora tener (Leschik) Mädler, 1964. 11. Patinasporites densus Leschik, 1955. 12. Ovalipollis pseudoalatus (Thiergart) Schuurman, 1976. 13 [START_REF] Van De Schootbrugge | A c c e p t e d M a n u s c r i p t Morbey[END_REF]. 5. Gordonispora fossulata (Balme 1970) Van Der Eem, 1983. 6. Nevesisporites vallatus de Jersey et Paten, 1964. 7. Lycopodiacidites kuepperi Klaus, 1960. 8, 9. Brodispora striata Clarke, 1965. 10. Lagenella martini (Leschik) Klaus, 1960. 11

  any biostratigraphic constraint. Gély and Lorenz (1991) identified the Hettangian-Sinemurian boundary (at 508.20 m) based on the lithostratigraphy and by correlating the logging tools throughout the Paris Basin. Only the occurrence of bioclastic limestone with Gryphaea, starting at a depth of 508.2 m, suggests the Sinemurian stage

  A c c e p t e d M a n u s c r i p t retrogradational trend from a distal braided alluvial fan (Gmm, Gh, St, Stb, Sh, and Shb facies association) and/or a fluvial sand sheet (Sh, Shb, Flb, and St facies association) within a shallow lake to lake environment (Flb and F facies association). The maximum flooding episodes are marked by massive bioturbated silty clays. However, the eleventh sequence records a well-developed progradational trend within a floodplain environment where dolomitic nodules attributed to dolocretes indicate the development of palaeosols (Fn and Dn facies).

  A c c e p t e d M a n u s c r i p tDuplicisporites granulatus (Leschik)[START_REF] Paracirculina | [END_REF], Illinites chitonoides Klaus, 1964, Microcachryidites doubingeri Klaus, 1964, Ovalipollis pseudoalatus (Thiergart) [START_REF] Thiergart) Schuurman | Ovalipollis pseudoalatus[END_REF][START_REF] Paracirculina | [END_REF], Porcellispora longdonensis (Clarke)[START_REF] Paracirculina | [END_REF] emend. Morbey, 1975, Praecirculina granifer (Leschik) Klaus, 1960, Quadraeculina anellaeformis Maljavkina, 1949, Samaropollenites speciosus Goubin, 1965, Staurosaccites quadrifidus Dolby, 1976, Triadispora epigona Klaus, 1964, Triadispora falcata Klaus, 1964, Triadispora plicata Klaus, 1964, Triadispora staplinii (Jansonius) Klaus, 1964, Triadispora suspecta Scheuring, 1970, Triadispora verrucata (Schulz) Scheuring, 1970, Alisporites sp., Calamospora sp., Chordasporites sp., Cycadopites sp., and Duplicisporites sp. The second palynological assemblage (SC-2: samples PC-27 to PC-38; Fig. 8) consists of: Alisporites grauvogeli Klaus, 1964, Aratrisporites granulatus Klaus, 1960, Camerosporites secatus Leschik, 1956, Duplicisporites granulatus (Leschik) Scheuring, 1970, Microcachryidites doubingeri Klaus, 1964, Ovalipollis pseudoalatus (Thiergart) Schuurman, 1976, Paracirculina scurrilis Scheuring, 1970, Paracirculina quadruplices Scheuring, 1970, Patinasporites densus Leschik, 1955, Porcellispora longdonensis (Clarke) Scheuring, 1970 emend. Morbey, 1975, Praecirculina granifer (Leschik) Klaus, 1960, Quadraeculina anellaeformis Maljavkina, 1949, Samaropollenites speciosus Goubin, 1965, Vallasporites ignacii Leschik, 1956, Alisporites sp., and Duplicisporites sp. The new palynological assemblage (SC-3: samples PC-39 to PC-41; Figs. 9, 10) yields an assemblage characterised by: Alisporites grauvogeli Klaus, 1964, Alisporites opii Daugherty, 1941, Anapiculalisporites spiniger (Leschik) Reinhardt, 1962, Aulisporites astigmosus (Leschik) Klaus, 1960, Brodispora striata Clarke, 1965, Calamospora tener (Leschik) Mädler, 1964, Camerosporites secatus Leschik, 1956, Cibotiumspora juriensis (Balme) Filatoff, 1975, Cingulizonates cf. rhaeticus (Rheinhardt) Schulz, 1967, Deltoidospora toralis A c c e p t e d M a n u s c r i p t (Leschik) Lund, 1977, Dictyophyllidites mortonii (de Jersey) Playford et Dettmann, 1965, Duplicisporites granulatus (Leschik) Scheuring, 1970, Gordonispora fossulata (Balme, 1970) Van Der Eem, 1983, Kraeuselisporites lituus (Leschik) Scheuring, 1974, Lagenella martini (Leschik) Klaus, 1960, Leptolepidites proxigranulatus (Brenner) Dörhöfer, 1979, Lycopodiacidites kuepperi Klaus, 1960, Lycopodiacidites rhaeticus Schulz, 1967, Nevesisporites vallatus de Jersey et Paten, 1964, Ovalipollis pseudoalatus (Thiergart) Schuurman, 1976, Paracirculina quadruplices Scheuring, 1970, Patinasporites densus Leschik, 1955, Praecirculina granifer (Leschik) Klaus, 1960, Schizaeoisporites worsleyi Bjaerke et Manum, 1977, Striatella seebergensis Mädler, 1964, Striatella scanica (Nilsson) Filatoff et Price, 1988, Striatoabieites aytugii (Visscher) Scheuring, 1970, Todisporites cinctus (Maljavkina) Orlowska-Zwolinska, 1971, Vallasporites ignacii Leschik, 1956, Vitreisporites pallidus (Reissinger) Nilsson, 1958, Alisporites sp., Aratrisporites sp., Calamospora sp., Cycadopites sp., Duplicisporites sp., Ephedripites sp., Todisporites sp., and Verrucosisporites sp.

  ): Aratrisporites paraspinosus Klaus, 1960, Carnisporites spiniger (Leschik) A c c e p t e d M a n u s c r i p t Morbey, 1975, Classopollis meyeriana (Klaus) de Jersey, 1973, Classopollis torosus (Reissinger) Balme, 1957, Convolutispora klukiforma (Nilsson) Schulz, 1967, Dapcodinium priscum Evitt, 1961, Granulatisporites infirmus (Balme) Cornet et Traverse, 1975, Kraeuselisporites reissingeri (Harris) Morbey, 1975, Kyrtomisporis speciosus Mädler, 1964, Ovalipollis pseudoalatus (Thiergart) Schuurman, 1976, Paracirculina scurrilis Scheuring, 1970, Patinasporites densus Leschik, 1955, Plaesiodictyon mosellanum Wille, 1970, Rhaetogonyaulax rhaetica (Sarjeant) Loeblich et Loeblich, 1968, Taurocusporites verrucatus Schulz, 1967, Uvaesporites argenteaeformis (Bolkhovitina) Schulz, 1967, Cibotiumspora sp., Cycadopites sp., Deltoidospora sp., Michrystridium sp., Psophosphaera sp., Uvaesporites sp., and Verrucosisporites sp.

  The SC-1 assemblage is Longobardian in age (late Ladinian) due to the presence of Camerosporites secatus, Duplicisporites granulatus, Microcachryidites doubingeri, Ovalipollis pseudoalalus, Paracirculina scurrilis, Porcelispora longdonensis, Triadispora epigona, Triadispora plicata, Triadispora staplinii, and Triadispora falcata. The assemblage presented in our study is equivalent to the "second assemblage" of Adloff et al. (1987). Their assemblage listed the following sporomorphs over the 712.60-710.05 m interval (unspecified levels): Triadispora aurea, Triadispora suspecta, Triadispora staplinii, Microcachryidites fastidioides, Pytiosporites sp., Alisporites sp., Ovalipollis pseudoalatus, Ovalipollis cultus, and Duplicisporites granulatus.

  The SC-2 assemblage is dated as Longobardian-Cordevolian transition to early Carnian (Ladinian-Carnian transition) in age due to the presence of Ladinian-Carnian sporomorphs such as Camerosporites secatus, Duplicisporites granulatus, Ovalipollis pseudoalatus, A c c e p t e d M a n u s c r i p t Microcachryidites doubingeri, Porcellispora longdonensis, and the occurrence of the typical Carnian taxa Paracirculina quadruplicis, Patinasporites densus and Vallasporites ignacii. The late Ladinian-Carnian period is characterised by a rapid diversification of Circumpollen taxa such as Camerosporites secatus, Duplicisporites granulatus and Praecirculina granifer, in association with the appearance of Patinasporites densus, Samaropollenites speciosus, and Vallasporites ignacii (Schuurman's phase I; Visscher and Krystyn, 1978; Visscher and

  The SC-3 assemblage is Cordevolian in age due to the co-occurrence of Aulisporites astigmosus and Lagenella martini -with a range restricted to the Cordevolian-early Tuvalian -together with typical late Ladinian-Carnian palynomorphs such as Camerosporites secatus and Duplicisporites granulatus, and the Carnian taxa Anapiculatisporites spiniger, Brodispora striata, Cibotiumspora juriensis, Kraeuselisporites lituus, Lycopodiacidites kuepperi, Paracirculina quadruplicis, Patinasporites densus, and Vallasporites ignacii. Lagenella martinii is known from an ammonoid-controlled succession of the Raibl Group,A c c e p t e d M a n u s c r i p t Southern Alps, and has been recorded in Europe starting from the Cordevolian (Van der Eem,

  s c r i p t homogeneous residue. Their work yielded a rich assemblage including Classopollis spp., Heliosporites reissingeri, Deltoidospora toralis, Taurocusporites verrucatus, Alisporites robustus, and Dapcodinium priscum. To propose an age, they use the debatable "criterion of absence" with the palynomorphs Ovalipollis pseudoalatus, Rhaetipollis germanicus, and

  2 m based on the paleontological data. Based on well-log correlations, the Triassic-Liassic boundary has been located at 548.5 m. Finally, these sedimentological and palynological high-resolution results from the Sancerre-Couy core establish a new reference section for the Permian to Triassic deposits of the Paris Basin. The present work will be of great help in further correlations with neighbouring Permian and Triassic outcrops or core-free borehole.

  s c r i p t basins", Dijon, France, pp. 120-121. Courtinat, B., Piriou, S., 2002. Les palynomorphes du Rhétien du bassin de Lodève : stratigraphie et environnements de dépôts. Géologie de la France 3, 3-16. Delmas, J., Houel, P., Vially, R., 2002. Paris Basin, Petroleum potential. IFP regional report. Doubinger, J., Adloff, M.C., 1977. Études palynologiques dans le Trias de la bordure sud-est du Massif central français (bassin de Largentiere, Ardèche). Sciences Géologiques 30(1), 59-74. Dunay, R.E., Fisher, M.J., 1978. The Karnian palynoflora succession in the Northern Calcareous Alps, Lunz am See, Austria. Pollen et Spores 20, 177-187. Echtler, H., Malavieille, J., 1990. Extensional tectonics, basement uplift and Stephano-Permian collapse basin in a late Variscan metamorphic core complex (Montagne Noire, southern Massif Central). Tectonophysics 177, 125-138. Fijałkowska-Mader, A., 1999. Palynostratigraphy, palaeoecology and palaeoclimatology of the Triassic in south-eastern Poland. Zentralblatt für Geologie und Paläontologie 1, 601-627. Fisher, M.J., Dunay, R.E., 1984. Palynology of the Petrified Forest Member of the Chinle Formation (Upper Triassic), Arizona, USA. Pollen et Spores 26, 241-284.

  Figure 1 A. Triassic and Permian outcrops and geological background in France, taken from

Figure 2

 2 Figure 2 Simplified sedimentary column of the Permian-Triassic-lower Jurassic deposits from

Figure 3

 3 Figure 3 Sedimentological section, depositional environment evolution and stratigraphic

Figure 4

 4 Figure 4 Sedimentological section, depositional environment evolution and stratigraphic

Figure 5

 5 Figure 5 Stratigraphic distribution of the palynological taxa in the study interval. Sample (1):

Figure 6

 6 Figure 6 SC-1 palynological assemblage. 1. Triadispora falcata Klaus, 1964. 2. Triadispora

Figure 7

 7 Figure 7 SC-1 palynological assemblage. 1. Microcachryidites doubingeri Klaus, 1964. 2.

  Calamospora tener (Leschik) Mädler, 1964. 12. Praecirculina granifer (Leschik)Klaus, 1960. 13, 14. Cycadopites sp. Scale bar: 10 µm.

Figure 8

 8 Figure 8 SC-2 palynological assemblage. 1. Alisporites grauvogeli Klaus, 1964. 2.

Figure 9

 9 Figure 9 SC-3 palynological assemblage. 1. Alisporites grauvogeli Klaus, 1964. 2. Alisporites

Figure 10

 10 Figure 10 SC-3 palynological assemblage. 1. Todisporites cinctus (Maljavkina) Orlowska-

Figure 12

 12 Figure 11 SC-4 palynological assemblage. 1. Granulatisporites infirmus (Balme) Cornet et

  s c r i p t previous studies based on well-log data. Table 1 Facies description and interpretation of the Permian and Triassic series in the Sancere

  . Striatella seebergensis Mädler, 1964. 14. Striatella scanica (Nilsson) Filatoff et Price, 1988. 15. Kraeuselisporites lituus (Leschik) Scheuring, 1974. 16. Praecirculina granifer (Leschik) Klaus, 1960. Scale bar: 10 µm.

.

  Ephedripites sp. 12.Verrucosisporites sp. 13. Schizaeoisporites worsleyiBjaerke et Manum, 1977. 14. Cingulizonates sp. cf. Cingulizonates rhaeticus (Rheinhardt) Schulz, 1967. 15.Lycopodiacidites rhaeticusSchulz, 1967. 16. Leptolepidites proxigranulatus (Brenner)Dörhöfer, 1979. 17. Anapiculalisporites spiniger (Leschik) Reinhardt, 1962. 18, 19.

	Cycadopites sp. Scale bar: 10 µm.
	M a n u s c r i p t
	A c c e p t e d

Acknowledgements

A c c e p t e d M a n u s c r i p t

The authors are grateful to Dr. Evelyn Kustatscher and an anonymous reviewer for helpful and constructive suggestions, and to the editor Dr. Borja Cascales-Miñana for his valuable recommendations. This research was supported by the CGL2014-52699P (Spanish Ministry) and GRC 2015/020 projects (Xunta de Galicia).


Xavier Delorme
email: delorme@emse.fr

Alexandre Dolgui
email: alexandre.dolgui@imt-atlantique.fr

Sergey Kovalev
email: skovalev@inseec.com

Mikhail Y Kovalyov
email: kovalyovmy@newman.bas-net.by

Minimizing the Number of Workers in a Paced Mixed-Model Assembly Line

Keywords: workforce assignment, production line, computational complexity, algorithms

We study a problem of minimizing the maximum number of identical workers over all cycles of a paced assembly line comprised of m stations and executing n parts of k types. There are lower and upper bounds on the workforce requirements and the cycle time constraints. We show that this problem is equivalent to the same problem without the cycle time constraints and with fixed workforce requirements. We prove that the problem is NP-hard in the strong sense if m = 3 and if m = 4 and the workforce requirements are station independent, and present an Integer Linear Programming model, an enumeration algorithm and a dynamic programming algorithm. Polynomial in k and polynomial in n algorithms for special cases with two part types or two stations are also given. The relation to the Bottleneck Traveling Salesman Problem and its generalizations are discussed.

Introduction

We study the following workforce planning problem. There is a paced assembly line with m stations at which parts of distinct types of a set P = {1, . . . , k} are manufactured. Each part visits the stations in the same order 1, . . . , m and fully occupies any station in the time period between its arrival and departure. With a time step C called the cycle time, a part at station i departs from this station and immediately arrives at station i + 1, i = 1, . . . , m -1, a new part arrives at station 1 and the part at station m leaves the line. Activities taking place between two successive part moves are called the production cycle. If part j is processed at station i in a production cycle, then the duration of all the operations on this part at this station in this cycle is a non-increasing function p ij (x ij ) of the number x ij of identical (fully skilled) workers assigned to station i and part j in this cycle. In the same cycle, workers assigned to different stations perform their operations in parallel. It is assumed that they do not move from one station to another in the same cycle. However, they can move instantly to another station after the cycle has finished. To be feasible with respect to the cycle time, the relation p ij (x ij ) ≤ C must be satisfied for each station and each part in each production cycle.

Besides, technological constraints define the lower and upper bounds on the values x ij in each cycle: 0 ≤ a ij ≤ x ij ≤ b ij , i = 1, . . . , m, j ∈ P . We assume, without loss of generality, that p ij (b ij ) ≤ C for all i and j.

A requirement of the global supply chain is that the production should keep a given proportion of the manufactured parts. To address this issue, the notion of a Minimal Part Set (MPS) is used, which was introduced into the operational research literature by Hitz [START_REF] Hitz | Scheduling of flow shops II[END_REF]. Let the part proportion be given by the numbers t 1 , . . . , t k , where t j is the percentage of type j parts to be manufactured, and let GCD denote the greatest common divisor of the numbers t 1 , . . . , t k .

Denote o j = t j /GCD, j ∈ P , and n = k j=1 o j . MPS is the multiset that consists of o j copies of each type j part, j ∈ P . Note that, for a given part proportion t 1 , . . . , t k , the numbers o 1 , . . . , o k and n are unique. In this paper, we represent MPS as the sequence (o 1 , . . . , o k ). According to the theory of computational complexity, this representation satisfies the conditions of a reasonable encoding scheme (Garey and Johnson [START_REF] Garey | Computers and intractability: A guide to the theory of NP-completeness[END_REF], p.10), while a representation that contains all n part copies does not satisfy these conditions.

An MPS sequence is a part sequence π = (j 1 , . . . , j n ), j r ∈ P , r = 1, . . . , n, in which each type j part occurs exactly o j times, j ∈ P . According to the MPS sequence π, the parts visit the line cyclically in the order j 1 , . . . , j n , j 1 , . . . , j n , . . .; see Fig. 1 for an illustration. In each production cycle, each station is assigned a part and this arrangement can be represented by a sequence σ = (j ′ 1 , . . . , j ′ m ), where j ′ h ∈ P is the part assigned to station m + 1 -h, h = 1, . . . , m. We call such an arrangement a P-cycle. For the example in Fig. 1, the current P-cycle is (j 1 , . . . , j m ) and the previous P-cycle is (j n , j 1 , . . . , j m-1 ).

Parts

Stations

. . . ✲ ✖✕ ✗✔ j 1 ✲ ✖✕ ✗✔ j n ✲ . . . ✲ ✖✕ ✗✔ j m+1 ✲ ✖✕ ✗✔ j m ✲ ✖✕ ✗✔ j m-1 ✲ . . . ✲ ✖✕ ✗✔ j 1 ✲ ✖✕ ✗✔ j n ✲ . . . 1 2 m . . .
Given the MPS sequence π = (j 1 , . . . , j n ), let us consider a directed graph G(π) with the set of vertices {j 1 , . . . , j n } and the set of arcs {(j 1 , j 2 ), (j 2 , j 3 ), . . . , (j n-1 , j n ), (j n , j 1 )}. Thus, G(π) is the graph called the (directed) cycle. We say that a P-cycle σ is π-feasible if and only if it is a walk in the graph G(π), with no vertex and arc repetition if m ≤ n. For example, if m = n + 1, then σ = (j 1 , . . . , j n , j 1 ) is π-feasible and, if m = 3, then σ = (j 6 , j 7 , j 8 ) is π-feasible. Let Φ(π) denote the set of all distinct π-feasible P-cycles. We have |Φ(π)| = n. Furthermore, let x (σ) i denote the number of workers assigned to station i in the P-cycle σ, i = 1, . . . , m. The total number of workers used in this P-cycle is equal to m i=1 x (σ) i . Denote by x the structure with the entries x (σ) i , i = 1, . . . , m, σ ∈ Φ(π). The total number of workers used in the long run of the MPS sequence π = (j 1 , . . . , j n ) is equal to

T (π, x) = max σ∈Φ(π) { m i=1 x (σ) i }.
The problem is to determine an MPS sequence π and the number of workers assigned to each station in each distinct P-cycle, determined by the structure x, such that the maximum total number of workers over all P-cycles, T (π, x), is minimized. We denote this problem as MinMaxSum.

Note that an MPS sequence can be described in many different ways, and there exist special cases of the MinMaxSum problem for which an optimal MPS sequence is described in O(k) time, see Section 7.

MinMaxSum problem is a subproblem of the industrial problem studied within European project "amePLM" (Battaïa et al. [START_REF] Battaïa | Workforce minimization for a mixed-model assembly line in the automotive industry[END_REF], Dolgui et al. [START_REF] Dolgui | Optimal workforce assignment to operations of a paced assembly line[END_REF]). In the industrial case, two or three automotive engines (two or three part types) are produced in the proportion of 75% and 25% in the case of two engines and 75% and 20% and 5% in the case of three engines on an assembly line comprising of 11 stations. Therefore, m = 11, k = 2 or k = 3 and (o 1 , o 2 ) = (3, 1) or [START_REF] Dauscha | On cyclic sequence types for constructing cyclic schedule[END_REF][START_REF] Bartholdi | Cyclic scheduling via integer programs with circular ones[END_REF][START_REF] Akagi | A method for assembly line balancing with more than one worker in each station[END_REF]. The processing time functions are station independent and inversely proportional to the number of workers: p ij (x) = p j /x, i = 1, . . . , m, j ∈ P . Each station can be assigned one, two, three or four workers, that is, a ij = 1 and b ij = 4 for all i and j. The cycle time is determined as the ratio of the total production time available in the planning horizon to the planned production volume in this horizon.

(o 1 , o 2 , o 3 ) =
In the next section, a review of the relevant literature is given. In Section 3, we demonstrate that the MinMaxSum problem is equivalent to the same problem without the cycle time constraints p ij (x ij ) ≤ C and with a ij = b ij = w ij for appropriately determined fixed workforce requirements w ij , i = 1, . . . , m, j ∈ P , for which we keep the same notation MinMaxSum. We

suggest an O min mnk n-1 , n!m (o 1 -1)!o 2 !•••o k !
time enumeration algorithm to solve this problem, which can be efficient if n is small. In Section 4, we provide a proof of the strong NP-hardness of the MinMaxSum problem in the case when m = 4 and the workforce requirements are station independent: w ij = w j , i = 1, . . . , m, j ∈ P . Obviously, if the workforce requirements are part type independent: w ij = w i , i = 1, . . . , m, j ∈ P , then all MPS sequences π have the same total workforce requirements T (π) = m i=1 w i . An O(n k+1 k 2m+2-k ) time dynamic programming algorithm for the MinMaxSum problem with n ≥ m is presented in Section 5. Section 6 contains an Integer Linear Programming (ILP) formulation of this problem. Polynomial in k and polynomial in n algorithms for three special cases with two part types or two stations are given in Section 7. The paper ends with a summary of the results and suggestions for future research.

Literature review

The MinMaxSum problem has much in common with the problem studied by Lee and Vairaktarakis [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF] and it is a special case of the problem studied by Winch et al. [START_REF] Winch | Cyclic job scheduling in paced assembly lines with cross-trained workers[END_REF]. However, [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF] and [START_REF] Winch | Cyclic job scheduling in paced assembly lines with cross-trained workers[END_REF] do not consider concise representation of the MPS assuming that all parts are of different types (k = n) and the workforce requirements are fixed (a ij = b ij , i = 1, . . . , m, j ∈ P ). Furthermore, [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF] assumes that the MPS sequence is not repeated cyclically: the line is free before the first part of an MPS sequence arrives at station 1 and the production stops when the last part of this sequence departs from station m.

We denote the problem in [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF] as Fix. Lee and Vairaktarakis proved that this problem is solvable in O(n log n) time if m = 2 and it is NP-hard in the strong sense if m = 3. They suggested an ILP formulation, lower bounds and heuristics for the general case of FIX. Note that an O(n log n) algorithm would be pseudo-polynomial with respect to the MinMaxSum problem. Vairaktarakis and Winch [START_REF] Vairaktarakis | Worker cross-training in paced assembly lines[END_REF] extended the results of Lee and Vairaktarakis [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF] to the case of partially skilled workers and the criterion of minimizing the costs of their crosstraining. They motivated their studies by the production of firetrucks. Vairaktarakis et al. [START_REF] Vairaktarakis | Workforce planning in synchronous production systems[END_REF] extended the results of [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF] to consider a different protocol of part processing, according to which each part requires a number of linearly ordered operations and each operation requires a specific station in a production cycle. The objective is to minimize a linear combination of the workforce cost and costs associated with the number of production cycles, which is one of the decision variables.

The workers in Winch et al. [START_REF] Winch | Cyclic job scheduling in paced assembly lines with cross-trained workers[END_REF] are not identical: each worker possesses certain skills, stations are partitioned into skill groups and a worker can be assigned to a station only if he possesses the skill that determines the skill group of this station. The MinMaxSum problem is a special case of the problem in [START_REF] Winch | Cyclic job scheduling in paced assembly lines with cross-trained workers[END_REF], in which each worker possesses all skills. Winch et al. [START_REF] Winch | Cyclic job scheduling in paced assembly lines with cross-trained workers[END_REF] proved that the MinMaxSum problem is NP-hard in the strong sense for m = 3 and they stated that the O(n log n) algorithm in [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF] can be adapted to solve the MinMaxSum problem with m = 2 in O(n log n) time. They also designed lower bounds, heuristic algorithms and an optimal branch-and-bound procedure for the general problem.

Academic studies of the workforce planning problems for production lines were initiated by Akagi et al. [START_REF] Akagi | A method for assembly line balancing with more than one worker in each station[END_REF] and Wilson [START_REF] Wilson | Formulation of a problem involving assembly lines with multiple manning of work stations[END_REF]. Recent surveys of the results in this field are given by Battaïa and Dolgui [START_REF] Battaïa | A taxonomy of line balancing problems and their solution approaches[END_REF], Battaïa et al. [START_REF] Battaïa | Workforce minimization for a mixed-model assembly line in the automotive industry[END_REF], De Bruecker et al. [START_REF] De Bruecker | Workforce planning incorporating skills: state of the art[END_REF] and Dolgui et al. [START_REF] Dolgui | Optimal workforce assignment to operations of a paced assembly line[END_REF]. Further information can be found in Vairaktarakis et al. [START_REF] Vairaktarakis | Level workforce planning for multistage transfer lines[END_REF], Polat et al. [START_REF] Polat | A two-phase variable neighbourhood search algorithm for assembly line worker assignment and balancing problem type-II: an industrial case study[END_REF], Dalle Mura and Dini [START_REF] Dalle Mura | Worker skills and equipment optimization in assembly line balancing by a genetic approach[END_REF],

Yilmas and Yilmas [START_REF] Yilmaz | A multi-manned assembly line balancing problem with classified teams: a new approach[END_REF], Zacharia and Nearchou [START_REF] Zacharia | A population-based algorithm for the bi-objective assembly line worker assignment and balancing problem[END_REF] and Ritt et al. [START_REF] Ritt | The assembly line worker assignment and balancing problem with stochastic worker availability[END_REF].

A close research area is cyclic scheduling and perfect periodic scheduling. In a cyclic scheduling problem, there is a set of jobs to be processed on a set of machines and each job must be repeated infinitely many times. A schedule must be found that repeats itself with a time step called the cycle time, satisfies a number of constraints and minimizes the cycle time. Levner et al. [START_REF] Levner | Complexity of cyclic scheduling problems: a state-of-the-art survey[END_REF] provided a survey of the computational complexity results for cyclic scheduling problems. The papers of Bartholdi et al. [START_REF] Bartholdi | Cyclic scheduling via integer programs with circular ones[END_REF], Dauscha et al. [START_REF] Dauscha | On cyclic sequence types for constructing cyclic schedule[END_REF], Chretienne [START_REF] Chretienne | The basic cyclic scheduling problem with deadlines[END_REF], Lutz and Davis [START_REF] Lutz | Development of operator assignment schedules: a DSS approach[END_REF], Hanen and Munier [START_REF] Hanen | Cyclic scheduling on parallel processors: on overview[END_REF], Kouvelis and Karabati [START_REF] Kouvelis | Cyclic scheduling in synchronous production lines[END_REF], Hall et al. [START_REF] Hall | The complexity of cyclic shop scheduling problems[END_REF], Timkovsky [START_REF] Timkovsky | Cycle shop scheduling[END_REF], Hochbaum and Levin [START_REF] Hochbaum | Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms[END_REF], Brucker and Kampmeyer [START_REF] Brucker | A general model for cyclic machine scheduling problems[END_REF], Kimbrel and Sviridenko [START_REF] Kimbrel | High-multiplicity cyclic job shop scheduling[END_REF],

Sawik [START_REF] Sawik | A mixed integer program for cyclic scheduling of flexible flow lines[END_REF], Che et al. [START_REF] Che | An efficient bicriteria algorithm for stable robotic flow shop scheduling[END_REF] and Bobrova and Servakh [START_REF] Bobrova | Construction of cyclic schedules in presence of parallel machines[END_REF] contain additional results. A perfect periodic scheduling problem is similar, but there is a frequency request for each job and the objective is to find a schedule that minimizes deviations from the frequencies in each cycle.

Perfect periodic scheduling problems have been studied by Bar-Noy et al. [START_REF] Bar-Noy | Efficient algorithms for periodic scheduling[END_REF], among others.

The MinMaxSum problem, when formulated in graph theoretical terminology, can be called a MinMaxSum Traveling Salesman Problem (MinMaxSum TSP). In this problem, a Hamiltonian cycle in a complete directed graph has to be found such that the maximum sum of weights of m consecutive vertices is minimized. The class of MinMaxSum TSPs intersects with the Bottleneck TSP (Gilmore and Gomory [START_REF] Gilmore | Sequencing a one state-variable machine: a solvable case of the traveling salesman problem[END_REF], Burkard and Sandholzer [START_REF] Burkard | Efficiently solvable special cases of bottleneck travelling salesman problems[END_REF], van der Veen [START_REF] Van Der Veen | An O(n) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices[END_REF], Burkard et al. [START_REF] Burkard | Well-solvable special cases of the traveling salesman problem: a survey[END_REF], Vairaktarakis [START_REF] Vairaktarakis | Simple algorithms for Gilmore-Gomory's traveling salesman and related problems[END_REF][START_REF] Vairaktarakis | On Gilmore-Gomory's open question for the bottleneck TSP[END_REF], Kabadi and Punnen [START_REF] Kabadi | The Bottleneck TSP[END_REF], LaRusic and Punnen [START_REF] Larusic | The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis[END_REF]) and the TSP under Categorization (Punnen [START_REF] Punnen | Traveling salesman problem under categorization[END_REF]), and it is also relevant to the k-Neighbor TSP (Woods et al. [START_REF] Woods | Linear time algorithm for the 3-neighbour traveling salesman problem on Halin graphs and extensions[END_REF]) and the Maximum Scatter TSP (Arkin et al. [START_REF] Arkin | On the maximum scatter traveling salesman problem[END_REF],

Chiang [START_REF] Chiang | New approximation results for the maximum scatter TSP[END_REF]).

Fixed workforce requirements and an enumeration algorithm

Consider an MPS sequence π. Observe that not all parts can be present in a P-cycle σ ∈ Φ(π), but, for any part, there is a P-cycle σ ∈ Φ(π) in which this part is present at any station.

This observation implies two statements: 1) the cycle time constraint and the lower and upper bounds on the number of workers are satisfied if and only if for each pair (i, j), i = 1, . . . , m, j ∈ P , there is a number of workers x such that p ij (x) ≤ C and a ij ≤ x ≤ b ij , and 2) the MinMaxSum problem is equivalent to the problem, in which, for each pair (i, j), the number of workers is fixed to be equal to

w ij := min{x | p ij (x) ≤ C, a ij ≤ x ≤ b ij }, i = 1, . . . , m, j ∈ P .
Recall that p ij (b ij ) ≤ C is assumed for all i and j. If the functions p ij (x) are invertible, then From now on, we assume that the MinMaxSum problem is to determine an MPS sequence π such that

w ij = max{a ij , ⌈p -1 ij (C)
T (π) = max F (σ) = m i=1 w m+1-i,j ′ i | σ = (j ′ 1 , . . . , j ′ m ) ∈ Φ(π)
is minimized. Let π * denote an optimal solution of this problem.

We now describe an enumeration algorithm for the MinMaxSum problem. Assume, without loss of generality, that o 1 = min i=1,...,k {o i }. Denote by Π the set of all MPS sequences, in which a copy of part 1 is in the first place. Note that we can limit our search of π * to these sequences because of the cyclic processing of parts. Let us evaluate the cardinality of this set. The number of sequences of length n -1 with copies of part 1 in o 1 -1 places is

equal to C o 1 -1 n-1 = (n-1)! (o 1 -1)!(n-o 1 )! .
For each sequence with all o 1 copies of part 1 placed, there are

C o 2 n-o 1 = (n-o 1 )! o 2 !(n-o 1 -o 2 )
! sequences with copies of part 2 in o 2 places. By continuing this line of reasoning,

|Π| = C o 1 -1 n-1 • C o 2 n-o 1 • • • C o k o k = (n -1)! (o 1 -1)!o 2 ! • • • o k ! .
On the other hand, since each component of a π ∈ Π can take one of the values 1, . . . , k,

|Π| ≤ k n-1 .
The

NP-hardness

Winch et al. [START_REF] Winch | Cyclic job scheduling in paced assembly lines with cross-trained workers[END_REF] prove that the MinMaxSum problem is NP-hard in the strong sense if m = 3.

The next theorem considers the case of station-independent workforce requirements, as they are in the industrial case that motivates our studies.

Theorem 1

The MinMaxSum problem is NP-hard in the strong sense if m = 4 and w ij = w j for i = 1, . . . , m and j ∈ P .

Proof: We will use a reduction from the NP-complete in the strong sense 3-Partition problem (Garey and Johnson [START_REF] Garey | Computers and intractability: A guide to the theory of NP-completeness[END_REF]).

3-Partition: Given 3q + 1 positive integer numbers e 1 , . . . , e 3q and E satisfying E/4 < e j < E/2, j = 1, . . . , 3q, and 3q j=1 e j = qE, is there a partition of the set {1, . . . , 3q} into subsets X 1 , . . . , X q such that j∈Xt e j = E for t = 1, . . . , q?

Given an instance of the 3-Partition problem, we construct the following instance of the MinMaxSum problem. There are m = 4 stations and k = 3q + 2 parts, among which there are 3q partition parts denoted 1, . . . , 3q and two enforcer parts denoted the E-part and the 0-part. The numerical parameters of the parts are: o j = 1 and w j = e j for the partition parts j = 1, . . . , 3q, o E = q and w E = E for the E-part, and o 0 = 6q and w 0 = 0 for the 0-part. We now show that there is an MPS sequence π ∈ Π for this instance with a value T (π) ≤ E if and only if the original instance of the 3-Partition problem has a solution.

Part "only if ". Let there be an MPS sequence π ∈ Π with a value T (π) ≤ E. Observe that in π each E-part must be immediately preceded by three 0-parts and immediately followed by three 0-parts, because otherwise there is a P-cycle in which an E-part and a partition part are simultaneously on the line and the total workforce requirement of this P-cycle is greater than E. Denote by X 1 , . . . , X q the sets of partition parts between two consecutive subsequences (0, 0, 0, E, 0, 0, 0) in π, where 0 denotes a 0-part and E denotes an E-part. Observe that each set X t consists of exactly three partition parts, because otherwise, by the Dirichlet principle, there is a set X t that includes four partition parts and these contribute more than E to T (π) when processed in the same P-cycle. In order to satisfy T (π) ≤ E, we must have j∈Xt w j = j∈Xt e j ≤ E, i = 1, . . . , q. Since q i=1 j∈Xt e j = E, we obtain j∈Xt e j = E, i = 1, . . . , q, as required for the proof of the part "only if".

Part "if ". Let X 1 , . . . , X q be a solution of the 3-Partition problem. Define the MPS sequence π = ([X 1 ], 0, 0, 0, E, 0, 0, 0, [X 2 ], . . . , 0, 0, 0, E, 0, 0, 0, [X q ], 0, 0, 0, E, 0, 0, 0), where [X t ] is an arbitrary sequence of the partition parts of the set X t , t = 1, . . . , q. Obviously, T (π) = E, as required for the proof of the part "if". Theorem 1 can be directly applied to prove that the Fix problem in Lee and Vairaktarakis [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF] is NP-hard in the strong sense if m = 4 and the workforce requirements are station-independent. The computational complexity of the case with m = 3 and the stationindependent workforce requirements is an open question for both the MinMaxSum and Fix problems.

Dynamic programming algorithm for the case n ≥ m

In this section, we assume that n ≥ m. The MinMaxSum problem can be formulated as the following constrained bottleneck path problem. There is a vertex weighted acyclic directed graph G = (V, A), in which the vertices are denoted as v = (v 1 , . . . , v m ) and correspond to the same P-cycles (v 1 , . . . , v m ), v i ∈ P , i = 1, . . . , m. There are n copies of each vertex. All the vertex copies are grouped into n same layers

L r = v = (v 1 , . . . , v m ) | v i ∈ P, i = 1, . . . , m , r = 1, . . . , n.
We have |L r | ≤ k m , r = 1, . . . , n. The arcs of the set A are defined as follows. There is

an arc (v, u) going from a vertex v ∈ L r to a vertex u ∈ L r+1 if and only if (v 2 , v 3 , . . . , v m ) = (u 1 , . . . , u m-1 ), 1 ≤ r ≤ n -1.
The existence of the latter arc means that the P-cycle u can immediately follow the P-cycle v when the same MPS sequence rotates along the stations.

A vector (o 1 (v), . . . , o k (v)) of o-weights is associated with each vertex v, whose components are equal to zero but the component o h (v) = 1 if v m = h, that is, if a copy of part type h is at the station 1 in the P-cycle v = (v 1 , . . . , v m ). A w-weight w(v) = m i=1 w i,v m+1-i is associated with each vertex v, which is the number of workers required for the P-cycle v = (v 1 , . . . , v m ).
The MinMaxSum problem reduces to the following constrained bottleneck problem, denoted as CBP, of finding a path σ = (v (1) , . . . , v (n) ), v (r) ∈ L r , in the graph G such that

(i) v (1) = (v (1) 1 , . . . , v (1)
m ), v (n) = (v (n) 1 , v (1) 1 , . . . , v (1)
m-1 ), (ii) v∈σ o h (v) = o h , h = 1, . . . ,

k, and

(iii) the maximum w-weight, max v∈σ w(v), is minimized.

Consider an arbitrary MPS sequence (j 1 , . . . , j n ). The requirement (i) states that if the first P-cycle of this sequence is (j 1 , . . . , j m ), then the last (n-th) P-cycle of this sequence must be (j n , j 1 , j 2 , . . . , j m-1 ). The requirement (ii) limits the search to the MPS sequences in which the number of occurrences of part type h is equal to o h , h ∈ P . The requirement (iii) addresses the criterion of minimizing the number of workers over all P-cycles.

The problem can be solved by the following dynamic programming algorithm, denoted as DP-CBP. For each pair of vertices v (1) and v (n) that satisfy (i), apply a standard dynamic programming technique that associates the value of a recursive function F r (v (1) , x 1 , . . . , x k , u (r) ) = max v∈σ w(v) with each (partial) path σ = (v (1) , u (2) , u (3) , . . . , u (r) ) from the vertex v (1) to a vertex u (r) ∈ L r , r = 2, 3, . . . , n. The arguments of this function, called the state variables or state, are defined such that x h = v∈σ o h (v) is the number of occurrences of the part type h in σ, h = 1, . . . , k, and u (r) is the last vertex of the path. The function F r represents the number of workers required for the first r number of P-cycles. It is clear that a partial path with the minimal value of F r (v (1) , x 1 , . . . , x k , u (r) ) dominates all the other partial paths in the same state (v (1) , x 1 , . . . , x k , u (r) ) in the sense that if a path in this state can be extended to a path including all n number of P-cycles and corresponding to an optimal MPS sequence, then the dominant path can do the same.

The initialization is F 1 (v (1) , a 1 , . . . , a k , v (1) ) = w(v (1) ), where a h is the number of occurrences of the part type h, h = 1, . . . , k, in the P-cycle v (1) , and F r (v (1) , x 1 , . . . , x k , u) = ∞ for r = 2, 3, . . . , n and all other states (v (1) , x 1 , . . . , x k , u). The recursion for x h ∈ {0, 1, . . . , o h } and

u (r) ∈ L r , r = 2, 3, . . . , n, is F r (v (1) , x 1 , . . . , x k , u (r) ) = min u (r-1) : u (r-1) ∈L r-1 ,(u (r-1) ,u (r) )∈A max F r-1 (v (1) , x 1 -o 1 (u (r) ), . . . , x k -o k (u (r) ), u (r-1) ), w(u (r) ) .
For a given v (1) and v (n) , the minimum number of workers is equal to F n (v (1) , o 1 , . . . , o k , v (n) )

and the corresponding MPS sequence can be found by backtracking. An optimal solution of the MinMaxSum problem has the minimum value F n (v (1) , o 1 , . . . , o k , v (n) ) over all the ordered pairs (v (1) , v (n) ) satisfying (i).

The running time of the algorithm DP-CBP can be evaluated as O(nT 1 T 2 T 3 ), where T 1 is the number of ordered pairs (v (1) , v (n) ) satisfying (i), T 2 is the number of distinct tuples (x 1 , . . . , x k , u (r) ), x h ∈ {0, 1, . . . , k}, u (r) ∈ L r , and T 3 is the number of vertices u (r-1) such that u (r-1) ∈ L r-1 and (u (r-1) , u (r) ) ∈ A for a given u (r) ∈ L r . We have

T 1 ≤ k m+1 , T 2 ≤ ( k h=1 o h ) max 1≤r≤n {|L r |} ≤ (n/k) k k m = n k k m-k and T 3 ≤ k.
Therefore, the running time of the algorithm DP-CBP is O(n k+1 k 2m+2-k ). If m and k are fixed, then the algorithm DP-CBP is pseudo-polynomial, which contributes to the computational complexity classification of the MinMaxSum problem.

Gilmore et al. [START_REF] Gilmore | Well-solved special cases[END_REF] provided an O(n 2 ) algorithm for the BTSP with costs such that c vu ≥ c v+1,u for all v and u. Re-number the part copies such that the workforce requirements at the second station satisfy w 0 2v ≥ w 0 2,v+1 , v = 1, . . . , n -1. Then c vu = w 0 2v + w 0 1u ≥ w 0 2,v+1 + w 0 1u = c v+1,u for all v and u. We deduce that the BTSP-W problem is solvable in O(n 2 ) time by the algorithm in [START_REF] Gilmore | Well-solved special cases[END_REF]. Furthermore, Vairaktarakis [START_REF] Vairaktarakis | Simple algorithms for Gilmore-Gomory's traveling salesman and related problems[END_REF] Gilmore et al. [START_REF] Gilmore | Well-solved special cases[END_REF] showed that (1, . . . , n) is an optimal solution of the BTSP if c vu ≥ c v+1,u and c vu ≤ c v,u+1 for all v and u. For the BTSP-WRA, we have c vu = w 0 2v +w 0 1u ≥ w 0 2,v+1 +w 0 1u = c v+1,u and c vu = w 0 2v + w 0 1u ≤ w 0 2v + w 0 1,u+1 = c v,u+1 for all v and u. Hence, (1, . . . , n) is an optimal solution of the BTSP-WRA. Observe that the sequence (1, . . . , n) can be represented using O(k) memory units because parts of the same type appear consecutively in it. Therefore, the BTSP-WRA can be solved in O(k) time.

Finally, consider the case of m = 2 and station-independent workforce requirements such that w 1j = w 2j = w j , j = 1, . . . , k. Note that this is a sub-case of the BTSP-WA, and therefore, it is solvable in O(n) time. Let w 0 v = w j if the part copy v is of type j. Number the part copies in the Least Workforce Requirement (LWR) order such that w 0 1 ≤ • • • ≤ w 0 n . We call the sequence of part copies π = (1, n, 2, n -1, 3, n -2, 4, . . . , ⌊n/2⌋, ⌊n/2⌋ + 1) including all n copies the Up-and-Down sequence. In this sequence, the part copy n -r + 2 is inserted between the part copies r -1 and r for r = 2, 3, . . . , ⌊n/2⌋.

Theorem 3

The Up-and-Down sequence is optimal for the MinMaxSum problem if m = 2 and w 1j = w 2j = w j , j = 1, . . . , k.

Proof: Let W * denote the optimal objective value for the MinMaxSum problem. We now show that W * ≥ w 0 n-r+1 + w 0 r+1 for r = 1, . . . , ⌊n/2⌋, which is sufficient for the proof. Since the part copy n with the largest workforce requirement appears on the line in two cycles with another part copy, W * ≥ w 0 n + w 0 2 must be satisfied. Assume that W * < w 0 n-1 + w 0 3 . It follows that, in the optimal sequence, the part copy n -1 appears on the line with the part copy 1 in one cycle and with the part copy 2 in the other cycle. Then the part copy n appears in the same cycle with the part copy i ≥ 3, and we obtain W * ≥ w 0 n + w 0 3 ≥ w 0 n-1 + w 0 3 , a contradiction. Assume that W * < w 0 n-2 + w 0 4 . It follows that, in the optimal sequence, the part copy n -2 appears on the line with a part copy from the set {1, 2, 3} in one cycle and with another part copy from this set in the other cycle. Then the part copy n or the part copy n -1 appears in the same cycle with the part copy i ≥ 4, and we obtain W * ≥ w 0 n-1 +w 0 4 ≥ w 0 n-2 +w 0 4 , a contradiction. Continuing in the same fashion, W * ≥ w 0 n-r+1 + w 0 r+1 for r = 1, . . . , ⌊n/2⌋, as required.

Observe that the Up-and-Down sequence can be represented using O(k) memory units because copies of the same part appear consecutively in the LWR order. This concise representation of the Up-and-Down sequence can be constructed in O(k log k) time by sorting the parts into the non-decreasing order of their workforce requirements and employing this order in the description of the Up-and-Down sequence of part copies. Thus, both the MinMaxSum problem with m = 2 and w ij = w j for i = 1, 2 and j = 1, . . . , k, and the BTSP-W with costs c vu = w 0 v + w 0 u for all v and u can be solved in O(k log k) time. Combining Lemma 1 and the latter result, we obtain the following corollary.

Conclusions and suggestions for future research

The algorithmic and computational complexity results for the MinMaxSum problem are summarized in Table 1.

For future research, it would be interesting to establish computational complexity of the following important special cases:

• fixed number of part types, for example, k = 2 or k = 3, and variable m and n,

• m = 3 and w ij = w j for all i and j,

Figure 1 :

 1 Figure 1: Parts moving according to an MPS sequence π = (j 1 , . . . , j n )

  ⌉}, where p -1 ij (y) is the inverse function of p ij (x). If the functions p ij (x) are not invertible, then w ij can be found in O(log 2 (b ij -a ij )) time by a bisection search over the range [a ij , b ij ]. Thus, in O(mk log 2 max i,j {b ij -a ij }) time, the MinMaxSum problem reduces to the equivalent problem without the cycle time constraints and with the fixed workforce requirements w ij , i = 1, . . . , m, j = 1, . . . , k.

  MinMaxSum problem reduces to calculating T (π * ) = min{T (π) | π ∈ Π}. Since |Φ(π)| = n, each value T (π) can be calculated in O(mn) time. Hence, the MinMaxSum problem can be solved in O(mn|Π|) = O min mnk n-1 , n!m (o 1 -1)!o 2 !•••o k ! time by calculating T (π) for all MPS sequences π ∈ Π. For example, if k = 2 then it can be solved in O min 2 n , n o 1 -1 mn time.

  developed an O(n log n) time algorithm for BTSP-W. The question of whether it can be solved in time polynomial in k is open. We say that the workforce requirements are agreeable if they satisfy w 11 ≥ • • • ≥ w 1k and w 21 ≥ • • • ≥ w 2k , and that they are reversely agreeable if they satisfy w 11 ≤ • • • ≤ w 1k and w 21 ≥ • • • ≥ w 2k . We denote the BTSP-W with agreeable and reversely agreeable workforce requirements as the BTSP-WA and the BTSP-WRA, respectively. van der Veen [43] developed an O(n) time algorithm for the BTSP with costs satisfying c vu ≥ c v+1,u and c vu ≥ c v,u+1 for all v and u. For the BTSP-WA, we have c vu = w 0 2v + w 0 1u ≥ w 0 2,v+1 + w 0 1u = c v+1,u and c vu = w 0 2v + w 0 1u ≥ w 0 2v + w 0 1,u+1 = c v,u+1 for all v and u. Hence, the BTSP-WA can be solved in O(n) time. The question of whether it can be solved in time polynomial in k is open.

Corollary 1

 1 If m = rn + 2 and w ij = w j , i = 1, . . . , m, j = 1, . . . , k, then the MinMaxSum problem can be solved in O(k log k) time.

Table 1 : 2 O( 1 ) 1 •

 1211 Computational complexity and algorithms for the MinMaxSum problem.Additional characteristics ComplexityReference General O min mnk n-1 , n!m (o 1 -1)!o 2 !•••o k ! Section 3 n ≥ m O(n k+1 k 2m+2-k ) Section 5 m = 3 Strongly NP-hard [45] m = 4, w ij = w j Strongly NP-hard Theorem 1 w ij = w i Any solution is optimal Section 1 k = 2, w i1 = w 1 , w i2 = w Section 7.1 m = 2 O(n log n) [37] m = 2, agreeable w ij O(n) Section 7.2 and [43] m = 2, reversely agreeable w ij O(k) Section 7.2 and [20] m = 2, w ij = w j O(k log k) Theorem 3 m = rn + 2, w ij = w j O(k log k) Corollary m = 2 with respect to the ordinary NP-hardness or the existence of an algorithm polynomial in k, • m = 2 and agreeable or proportional (w 2j = aw 1j for a > 0) workforce requirements with respect to the ordinary NP-hardness or the existence of an algorithm polynomial in k. To resolve open questions, links with the BTSP and MinMaxSum TSPs could be further investigated. The development of exact and approximate solution methods for the general Min-MaxSum problem and computer experiments with them are both interesting and practically relevant topics.

ILP formulation

It is convenient to use the modulo operation mod (g, n) such that mod (g, n) = b if g = ⌊a/n⌋n + b and g, n and b are positive integer numbers. Since the divisor is always n in this paper, we simplify the modulo operation notation to g , g = mod (g, n). The MinMaxSum problem can be formulated as the following integer linear programming problem denoted as ILP. Denote the set of non-negative integer numbers by Z 0 . Introduce the non-negative integer variable T (total workforce requirement) and 0-1 variables y jp such that y jp = 1 if and only if a copy of part type p is in position j of an MPS sequence.

ILP problem: min T, subject to k p=1 (w 1p y j p + w 2p y j+1 p + • • • + w mp y j+m-1 p ) ≤ T, j = 1, . . . , n,

T ∈ Z 0 , y jp ∈ Z 0 , j = 1, . . . , n, p = 1, . . . , k.

The left-hand side of the constraints (1) represents the total workforce requirement for each of the n distinct P-cycles of an MPS sequence. The relation in (1) for j = 1 addresses the case when station 1 is occupied by the first part copy of an MPS sequence, for j = 2 it addresses the case when station 1 is occupied by the second part copy of this sequence, and so on.

Constraints (2) guarantee that each position of an MPS sequence is occupied by exactly one part copy. Constraints (3) require that the number of positions occupied by the copies of part type p is equal to o p for each p. The ILP problem has nk + 1 variables and 2n + k constraints.

Both dimensions are pseudo-polynomial because of n = k j=1 o j . It is unknown if there exists an ILP formulation with the independent of n number of variables and constraints. The ILP problem is similar to that given by Lee and Vairaktarakis [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF], but not the same.

Polynomially and pseudo-polynomially solvable cases

In sub-section 7.1, we suggest an O(1) time algorithm for the case of two part types and station independent workforce requirements, i.e. k = 2 and w i1 = w 1 , w i2 = w 2 , i = 1, . . . , m. In sub-section 7.2, we consider the case of m = 2. We show that this case reduces to a specific Thus, δ = mod (m, n). We will show that this general case reduces to the case with r = 0. Assume that r ≥ 1. Consider an arbitrary MPS sequence (j 1 , . . . , j n ) and an arbitrary Pcycle, in which part copies j δ , . . . , j 1 occupy stations 1, . . . , δ, respectively, and r same sets of the n part copies j n , j n-1 , . . . , j 1 occupy rn stations m -δ, m -δ + 1, . . . , m, respectively.

Denote the multiset of the part copies assigned to the stations m -δ, m -δ + 1, . . . , m as M . In the next P-cycle, the part copy j 1 leaves the last station m and the same part copy j 1 arrives at the station m -δ. The multiset M does not change. It is clear that it is the same in each of the n distinct P-cycles. Since the workforce requirements are station-independent, the contribution of the multiset M to the objective function is equal to F M = r k j=1 w j o j . The remaining contribution is determined by the P-cycles for the first δ stations. Denote the minimum workforce requirement for the problem with δ stations as F δ . Since the stations are identical, the minimum workforce requirement for the original problem with rn + δ stations is

In one of the industrial cases, m = 11, k = 2 and n = o 1 + o 2 = 4. Due to Lemma 1, this case reduces to the same case with m = 3.

Two part types

In this sub-section, we study the case in which k = 2, w i1 = w 1 , w i2 = w 2 , i = 1, . . . , m, and n ≥ m. It is the model for one of the industrial cases. If w 1 = w 2 , then any MPS sequence is optimal. Assume, without loss of generality, that w 1 > w 2 . To facilitate further discussion, we now present an integer linear programming formulation for this case, which is an adaptation of the ILP problem in Section 6. It is denoted as

Introduce 0-1 variables z j such that z j = 1 (z j = 0) if a copy of part type 1 (part type 2) is in position j of an MPS sequence. Denote z = (z 1 , . . . , z n ). Re-call that g = mod (g, n).

With the variables z j , the constraint in (1) for a given j transforms to

T ∈ Z 0 , z j ∈ {0, 1}, j = 1, . . . , n.

It can easily be seen that the ILP(k = 2, w ij = w j , n ≥ m) problem is equivalent to minimizing G(z) = max j=1,...,n {A j (z)}, subject to ( 6) and the 0-1 constraints. Denote the optimal objective function value of this problem as G * . Let us represent constraints (5) in the matrix form as Az ≤ v. An example of the matrix A for m = 3 and n = 9 is given below.

1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 Given a 0-1 vector z, we call index j selected if z j = 1.

Theorem 2

The vector z * , in which the selected indices are i•n o 1 , i = 1, . . . , o 1 , is an optimal solution of the ILP(k = 2, w ij = w j , n ≥ m) problem.

Proof: Consider z * . Let us evaluate the largest selected index among 1, . . . , j +m-1, which we denote as

n , which means that there exists z such that Az < v 0 and n j=1 z j = o 1 , where v 0 is the transposed vector

Two stations

In this sub-section, we assume that m = 2. The Bottleneck Traveling Salesman Problem (BTSP) can be formulated as follows. There is a complete directed graph with n vertices and arc costs c vu . The problem is to find a Hamiltonian cycle such that the maximum arc cost in this cycle is minimized. Let the part copies be numbered 1, . . . , n. It is clear that the Min-MaxSum problem with m = 2 is equivalent to the BTSP with the arc costs c vu = w 0 2v + w 0 1u , where w 0 iv = w ij , i = 1, 2, if the part copy v is of type j. We denote this problem as the BTSP-W.